Python/bltinmodule.c

   1 /* Built-in functions */
   2
   3 #include "Python.h"
   4
   5 #include "node.h"
   6 #include "code.h"
   7 #include "eval.h"
   8
   9 #include <ctype.h>
  10
  11 #ifdef RISCOS
  12 #include "unixstuff.h"
  13 #endif
  14
  15 /* The default encoding used by the platform file system APIs
  16    Can remain NULL for all platforms that don't have such a concept
  17 */
  18 #if defined(MS_WINDOWS) && defined(HAVE_USABLE_WCHAR_T)
  19 const char *Py_FileSystemDefaultEncoding = "mbcs";
  20 #elif defined(__APPLE__)
  21 const char *Py_FileSystemDefaultEncoding = "utf-8";
  22 #else
  23 const char *Py_FileSystemDefaultEncoding = NULL; /* use default */
  24 #endif
  25
  26 /* Forward */
  27 static PyObject *filterstring(PyObject *, PyObject *);
  28 #ifdef Py_USING_UNICODE
  29 static PyObject *filterunicode(PyObject *, PyObject *);
  30 #endif
  31 static PyObject *filtertuple (PyObject *, PyObject *);
  32
  33 static PyObject *
  34 builtin___import__(PyObject *self, PyObject *args, PyObject *kwds)
  35 {
  36         static char *kwlist[] = {"name", "globals", "locals", "fromlist",
  37                                  "level", 0};
  38         char *name;
  39         PyObject *globals = NULL;
  40         PyObject *locals = NULL;
  41         PyObject *fromlist = NULL;
  42         int level = -1;
  43
  44         if (!PyArg_ParseTupleAndKeywords(args, kwds, "s|OOOi:__import__",
  45                         kwlist, &name, &globals, &locals, &fromlist, &level))
  46                 return NULL;
  47         return PyImport_ImportModuleLevel(name, globals, locals,
  48                                           fromlist, level);
  49 }
  50
  51 PyDoc_STRVAR(import_doc,
  52 "__import__(name, globals={}, locals={}, fromlist=[], level=-1) -> module\n\
  53 \n\
  54 Import a module.  The globals are only used to determine the context;\n\
  55 they are not modified.  The locals are currently unused.  The fromlist\n\
  56 should be a list of names to emulate ``from name import ...'', or an\n\
  57 empty list to emulate ``import name''.\n\
  58 When importing a module from a package, note that __import__('A.B', ...)\n\
  59 returns package A when fromlist is empty, but its submodule B when\n\
  60 fromlist is not empty.  Level is used to determine whether to perform \n\
  61 absolute or relative imports.  -1 is the original strategy of attempting\n\
  62 both absolute and relative imports, 0 is absolute, a positive number\n\
  63 is the number of parent directories to search relative to the current module.");
  64
  65
  66 static PyObject *
  67 builtin_abs(PyObject *self, PyObject *v)
  68 {
  69         return PyNumber_Absolute(v);
  70 }
  71
  72 PyDoc_STRVAR(abs_doc,
  73 "abs(number) -> number\n\
  74 \n\
  75 Return the absolute value of the argument.");
  76
  77 static PyObject *
  78 builtin_all(PyObject *self, PyObject *v)
  79 {
  80         PyObject *it, *item;
  81         PyObject *(*iternext)(PyObject *);
  82         int cmp;
  83
  84         it = PyObject_GetIter(v);
  85         if (it == NULL)
  86                 return NULL;
  87         iternext = *Py_TYPE(it)->tp_iternext;
  88
  89         for (;;) {
  90                 item = iternext(it);
  91                 if (item == NULL)
  92                         break;
  93                 cmp = PyObject_IsTrue(item);
  94                 Py_DECREF(item);
  95                 if (cmp < 0) {
  96                         Py_DECREF(it);
  97                         return NULL;
  98                 }
  99                 if (cmp == 0) {
 100                         Py_DECREF(it);
 101                         Py_RETURN_FALSE;
 102                 }
 103         }
 104         Py_DECREF(it);
 105         if (PyErr_Occurred()) {
 106                 if (PyErr_ExceptionMatches(PyExc_StopIteration))
 107                         PyErr_Clear();
 108                 else
 109                         return NULL;
 110         }
 111         Py_RETURN_TRUE;
 112 }
 113
 114 PyDoc_STRVAR(all_doc,
 115 "all(iterable) -> bool\n\
 116 \n\
 117 Return True if bool(x) is True for all values x in the iterable.");
 118
 119 static PyObject *
 120 builtin_any(PyObject *self, PyObject *v)
 121 {
 122         PyObject *it, *item;
 123         PyObject *(*iternext)(PyObject *);
 124         int cmp;
 125
 126         it = PyObject_GetIter(v);
 127         if (it == NULL)
 128                 return NULL;
 129         iternext = *Py_TYPE(it)->tp_iternext;
 130
 131         for (;;) {
 132                 item = iternext(it);
 133                 if (item == NULL)
 134                         break;
 135                 cmp = PyObject_IsTrue(item);
 136                 Py_DECREF(item);
 137                 if (cmp < 0) {
 138                         Py_DECREF(it);
 139                         return NULL;
 140                 }
 141                 if (cmp == 1) {
 142                         Py_DECREF(it);
 143                         Py_RETURN_TRUE;
 144                 }
 145         }
 146         Py_DECREF(it);
 147         if (PyErr_Occurred()) {
 148                 if (PyErr_ExceptionMatches(PyExc_StopIteration))
 149                         PyErr_Clear();
 150                 else
 151                         return NULL;
 152         }
 153         Py_RETURN_FALSE;
 154 }
 155
 156 PyDoc_STRVAR(any_doc,
 157 "any(iterable) -> bool\n\
 158 \n\
 159 Return True if bool(x) is True for any x in the iterable.");
 160
 161 static PyObject *
 162 builtin_apply(PyObject *self, PyObject *args)
 163 {
 164         PyObject *func, *alist = NULL, *kwdict = NULL;
 165         PyObject *t = NULL, *retval = NULL;
 166
 167         if (Py_Py3kWarningFlag &&
 168             PyErr_Warn(PyExc_DeprecationWarning,
 169                        "apply() not supported in 3.x") < 0)
 170                 return NULL;
 171
 172         if (!PyArg_UnpackTuple(args, "apply", 1, 3, &func, &alist, &kwdict))
 173                 return NULL;
 174         if (alist != NULL) {
 175                 if (!PyTuple_Check(alist)) {
 176                         if (!PySequence_Check(alist)) {
 177                                 PyErr_Format(PyExc_TypeError,
 178                                      "apply() arg 2 expected sequence, found %s",
 179                                              alist->ob_type->tp_name);
 180                                 return NULL;
 181                         }
 182                         t = PySequence_Tuple(alist);
 183                         if (t == NULL)
 184                                 return NULL;
 185                         alist = t;
 186                 }
 187         }
 188         if (kwdict != NULL && !PyDict_Check(kwdict)) {
 189                 PyErr_Format(PyExc_TypeError,
 190                              "apply() arg 3 expected dictionary, found %s",
 191                              kwdict->ob_type->tp_name);
 192                 goto finally;
 193         }
 194         retval = PyEval_CallObjectWithKeywords(func, alist, kwdict);
 195   finally:
 196         Py_XDECREF(t);
 197         return retval;
 198 }
 199
 200 PyDoc_STRVAR(apply_doc,
 201 "apply(object[, args[, kwargs]]) -> value\n\
 202 \n\
 203 Call a callable object with positional arguments taken from the tuple args,\n\
 204 and keyword arguments taken from the optional dictionary kwargs.\n\
 205 Note that classes are callable, as are instances with a __call__() method.\n\
 206 \n\
 207 Deprecated since release 2.3. Instead, use the extended call syntax:\n\
 208     function(*args, **keywords).");
 209
 210
 211 static PyObject *
 212 builtin_callable(PyObject *self, PyObject *v)
 213 {
 214         if (Py_Py3kWarningFlag &&
 215             PyErr_Warn(PyExc_DeprecationWarning,
 216                        "callable() not supported in 3.x") < 0)
 217                 return NULL;
 218         return PyBool_FromLong((long)PyCallable_Check(v));
 219 }
 220
 221 PyDoc_STRVAR(callable_doc,
 222 "callable(object) -> bool\n\
 223 \n\
 224 Return whether the object is callable (i.e., some kind of function).\n\
 225 Note that classes are callable, as are instances with a __call__() method.");
 226
 227
 228 static PyObject *
 229 builtin_filter(PyObject *self, PyObject *args)
 230 {
 231         PyObject *func, *seq, *result, *it, *arg;
 232         Py_ssize_t len;   /* guess for result list size */
 233         register Py_ssize_t j;
 234
 235         if (!PyArg_UnpackTuple(args, "filter", 2, 2, &func, &seq))
 236                 return NULL;
 237
 238         /* Strings and tuples return a result of the same type. */
 239         if (PyString_Check(seq))
 240                 return filterstring(func, seq);
 241 #ifdef Py_USING_UNICODE
 242         if (PyUnicode_Check(seq))
 243                 return filterunicode(func, seq);
 244 #endif
 245         if (PyTuple_Check(seq))
 246                 return filtertuple(func, seq);
 247
 248         /* Pre-allocate argument list tuple. */
 249         arg = PyTuple_New(1);
 250         if (arg == NULL)
 251                 return NULL;
 252
 253         /* Get iterator. */
 254         it = PyObject_GetIter(seq);
 255         if (it == NULL)
 256                 goto Fail_arg;
 257
 258         /* Guess a result list size. */
 259         len = _PyObject_LengthHint(seq, 8);
 260
 261         /* Get a result list. */
 262         if (PyList_Check(seq) && seq->ob_refcnt == 1) {
 263                 /* Eww - can modify the list in-place. */
 264                 Py_INCREF(seq);
 265                 result = seq;
 266         }
 267         else {
 268                 result = PyList_New(len);
 269                 if (result == NULL)
 270                         goto Fail_it;
 271         }
 272
 273         /* Build the result list. */
 274         j = 0;
 275         for (;;) {
 276                 PyObject *item;
 277                 int ok;
 278
 279                 item = PyIter_Next(it);
 280                 if (item == NULL) {
 281                         if (PyErr_Occurred())
 282                                 goto Fail_result_it;
 283                         break;
 284                 }
 285
 286                 if (func == (PyObject *)&PyBool_Type || func == Py_None) {
 287                         ok = PyObject_IsTrue(item);
 288                 }
 289                 else {
 290                         PyObject *good;
 291                         PyTuple_SET_ITEM(arg, 0, item);
 292                         good = PyObject_Call(func, arg, NULL);
 293                         PyTuple_SET_ITEM(arg, 0, NULL);
 294                         if (good == NULL) {
 295                                 Py_DECREF(item);
 296                                 goto Fail_result_it;
 297                         }
 298                         ok = PyObject_IsTrue(good);
 299                         Py_DECREF(good);
 300                 }
 301                 if (ok) {
 302                         if (j < len)
 303                                 PyList_SET_ITEM(result, j, item);
 304                         else {
 305                                 int status = PyList_Append(result, item);
 306                                 Py_DECREF(item);
 307                                 if (status < 0)
 308                                         goto Fail_result_it;
 309                         }
 310                         ++j;
 311                 }
 312                 else
 313                         Py_DECREF(item);
 314         }
 315
 316
 317         /* Cut back result list if len is too big. */
 318         if (j < len && PyList_SetSlice(result, j, len, NULL) < 0)
 319                 goto Fail_result_it;
 320
 321         Py_DECREF(it);
 322         Py_DECREF(arg);
 323         return result;
 324
 325 Fail_result_it:
 326         Py_DECREF(result);
 327 Fail_it:
 328         Py_DECREF(it);
 329 Fail_arg:
 330         Py_DECREF(arg);
 331         return NULL;
 332 }
 333
 334 PyDoc_STRVAR(filter_doc,
 335 "filter(function or None, sequence) -> list, tuple, or string\n"
 336 "\n"
 337 "Return those items of sequence for which function(item) is true.  If\n"
 338 "function is None, return the items that are true.  If sequence is a tuple\n"
 339 "or string, return the same type, else return a list.");
 340
 341 static PyObject *
 342 builtin_chr(PyObject *self, PyObject *args)
 343 {
 344         long x;
 345         char s[1];
 346
 347         if (!PyArg_ParseTuple(args, "l:chr", &x))
 348                 return NULL;
 349         if (x < 0 || x >= 256) {
 350                 PyErr_SetString(PyExc_ValueError,
 351                                 "chr() arg not in range(256)");
 352                 return NULL;
 353         }
 354         s[0] = (char)x;
 355         return PyString_FromStringAndSize(s, 1);
 356 }
 357
 358 PyDoc_STRVAR(chr_doc,
 359 "chr(i) -> character\n\
 360 \n\
 361 Return a string of one character with ordinal i; 0 <= i < 256.");
 362
 363
 364 #ifdef Py_USING_UNICODE
 365 static PyObject *
 366 builtin_unichr(PyObject *self, PyObject *args)
 367 {
 368         long x;
 369
 370         if (!PyArg_ParseTuple(args, "l:unichr", &x))
 371                 return NULL;
 372
 373         return PyUnicode_FromOrdinal(x);
 374 }
 375
 376 PyDoc_STRVAR(unichr_doc,
 377 "unichr(i) -> Unicode character\n\
 378 \n\
 379 Return a Unicode string of one character with ordinal i; 0 <= i <= 0x10ffff.");
 380 #endif
 381
 382
 383 static PyObject *
 384 builtin_cmp(PyObject *self, PyObject *args)
 385 {
 386         PyObject *a, *b;
 387         int c;
 388
 389         if (!PyArg_UnpackTuple(args, "cmp", 2, 2, &a, &b))
 390                 return NULL;
 391         if (PyObject_Cmp(a, b, &c) < 0)
 392                 return NULL;
 393         return PyInt_FromLong((long)c);
 394 }
 395
 396 PyDoc_STRVAR(cmp_doc,
 397 "cmp(x, y) -> integer\n\
 398 \n\
 399 Return negative if x<y, zero if x==y, positive if x>y.");
 400
 401
 402 static PyObject *
 403 builtin_coerce(PyObject *self, PyObject *args)
 404 {
 405         PyObject *v, *w;
 406         PyObject *res;
 407
 408         if (Py_Py3kWarningFlag &&
 409             PyErr_Warn(PyExc_DeprecationWarning,
 410                        "coerce() not supported in 3.x") < 0)
 411                 return NULL;
 412
 413         if (!PyArg_UnpackTuple(args, "coerce", 2, 2, &v, &w))
 414                 return NULL;
 415         if (PyNumber_Coerce(&v, &w) < 0)
 416                 return NULL;
 417         res = PyTuple_Pack(2, v, w);
 418         Py_DECREF(v);
 419         Py_DECREF(w);
 420         return res;
 421 }
 422
 423 PyDoc_STRVAR(coerce_doc,
 424 "coerce(x, y) -> (x1, y1)\n\
 425 \n\
 426 Return a tuple consisting of the two numeric arguments converted to\n\
 427 a common type, using the same rules as used by arithmetic operations.\n\
 428 If coercion is not possible, raise TypeError.");
 429
 430 static PyObject *
 431 builtin_compile(PyObject *self, PyObject *args, PyObject *kwds)
 432 {
 433         char *str;
 434         char *filename;
 435         char *startstr;
 436         int start;
 437         int dont_inherit = 0;
 438         int supplied_flags = 0;
 439         PyCompilerFlags cf;
 440         PyObject *result = NULL, *cmd, *tmp = NULL;
 441         Py_ssize_t length;
 442         static char *kwlist[] = {"source", "filename", "mode", "flags",
 443                                  "dont_inherit", NULL};
 444
 445         if (!PyArg_ParseTupleAndKeywords(args, kwds, "Oss|ii:compile",
 446                                          kwlist, &cmd, &filename, &startstr,
 447                                          &supplied_flags, &dont_inherit))
 448                 return NULL;
 449
 450         cf.cf_flags = supplied_flags;
 451
 452 #ifdef Py_USING_UNICODE
 453         if (PyUnicode_Check(cmd)) {
 454                 tmp = PyUnicode_AsUTF8String(cmd);
 455                 if (tmp == NULL)
 456                         return NULL;
 457                 cmd = tmp;
 458                 cf.cf_flags |= PyCF_SOURCE_IS_UTF8;
 459         }
 460 #endif
 461         if (PyObject_AsReadBuffer(cmd, (const void **)&str, &length))
 462                 return NULL;
 463         if ((size_t)length != strlen(str)) {
 464                 PyErr_SetString(PyExc_TypeError,
 465                                 "compile() expected string without null bytes");
 466                 goto cleanup;
 467         }
 468
 469         if (strcmp(startstr, "exec") == 0)
 470                 start = Py_file_input;
 471         else if (strcmp(startstr, "eval") == 0)
 472                 start = Py_eval_input;
 473         else if (strcmp(startstr, "single") == 0)
 474                 start = Py_single_input;
 475         else {
 476                 PyErr_SetString(PyExc_ValueError,
 477                    "compile() arg 3 must be 'exec' or 'eval' or 'single'");
 478                 goto cleanup;
 479         }
 480
 481         if (supplied_flags &
 482             ~(PyCF_MASK | PyCF_MASK_OBSOLETE | PyCF_DONT_IMPLY_DEDENT | PyCF_ONLY_AST))
 483         {
 484                 PyErr_SetString(PyExc_ValueError,
 485                                 "compile(): unrecognised flags");
 486                 goto cleanup;
 487         }
 488         /* XXX Warn if (supplied_flags & PyCF_MASK_OBSOLETE) != 0? */
 489
 490         if (!dont_inherit) {
 491                 PyEval_MergeCompilerFlags(&cf);
 492         }
 493         result = Py_CompileStringFlags(str, filename, start, &cf);
 494 cleanup:
 495         Py_XDECREF(tmp);
 496         return result;
 497 }
 498
 499 PyDoc_STRVAR(compile_doc,
 500 "compile(source, filename, mode[, flags[, dont_inherit]]) -> code object\n\
 501 \n\
 502 Compile the source string (a Python module, statement or expression)\n\
 503 into a code object that can be executed by the exec statement or eval().\n\
 504 The filename will be used for run-time error messages.\n\
 505 The mode must be 'exec' to compile a module, 'single' to compile a\n\
 506 single (interactive) statement, or 'eval' to compile an expression.\n\
 507 The flags argument, if present, controls which future statements influence\n\
 508 the compilation of the code.\n\
 509 The dont_inherit argument, if non-zero, stops the compilation inheriting\n\
 510 the effects of any future statements in effect in the code calling\n\
 511 compile; if absent or zero these statements do influence the compilation,\n\
 512 in addition to any features explicitly specified.");
 513
 514 static PyObject *
 515 builtin_dir(PyObject *self, PyObject *args)
 516 {
 517         PyObject *arg = NULL;
 518
 519         if (!PyArg_UnpackTuple(args, "dir", 0, 1, &arg))
 520                 return NULL;
 521         return PyObject_Dir(arg);
 522 }
 523
 524 PyDoc_STRVAR(dir_doc,
 525 "dir([object]) -> list of strings\n"
 526 "\n"
 527 "If called without an argument, return the names in the current scope.\n"
 528 "Else, return an alphabetized list of names comprising (some of) the attributes\n"
 529 "of the given object, and of attributes reachable from it.\n"
 530 "If the object supplies a method named __dir__, it will be used; otherwise\n"
 531 "the default dir() logic is used and returns:\n"
 532 "  for a module object: the module's attributes.\n"
 533 "  for a class object:  its attributes, and recursively the attributes\n"
 534 "    of its bases.\n"
 535 "  for any other object: its attributes, its class's attributes, and\n"
 536 "    recursively the attributes of its class's base classes.");
 537
 538 static PyObject *
 539 builtin_divmod(PyObject *self, PyObject *args)
 540 {
 541         PyObject *v, *w;
 542
 543         if (!PyArg_UnpackTuple(args, "divmod", 2, 2, &v, &w))
 544                 return NULL;
 545         return PyNumber_Divmod(v, w);
 546 }
 547
 548 PyDoc_STRVAR(divmod_doc,
 549 "divmod(x, y) -> (div, mod)\n\
 550 \n\
 551 Return the tuple ((x-x%y)/y, x%y).  Invariant: div*y + mod == x.");
 552
 553
 554 static PyObject *
 555 builtin_eval(PyObject *self, PyObject *args)
 556 {
 557         PyObject *cmd, *result, *tmp = NULL;
 558         PyObject *globals = Py_None, *locals = Py_None;
 559         char *str;
 560         PyCompilerFlags cf;
 561
 562         if (!PyArg_UnpackTuple(args, "eval", 1, 3, &cmd, &globals, &locals))
 563                 return NULL;
 564         if (locals != Py_None && !PyMapping_Check(locals)) {
 565                 PyErr_SetString(PyExc_TypeError, "locals must be a mapping");
 566                 return NULL;
 567         }
 568         if (globals != Py_None && !PyDict_Check(globals)) {
 569                 PyErr_SetString(PyExc_TypeError, PyMapping_Check(globals) ?
 570                         "globals must be a real dict; try eval(expr, {}, mapping)"
 571                         : "globals must be a dict");
 572                 return NULL;
 573         }
 574         if (globals == Py_None) {
 575                 globals = PyEval_GetGlobals();
 576                 if (locals == Py_None)
 577                         locals = PyEval_GetLocals();
 578         }
 579         else if (locals == Py_None)
 580                 locals = globals;
 581
 582         if (globals == NULL || locals == NULL) {
 583                 PyErr_SetString(PyExc_TypeError,
 584                         "eval must be given globals and locals "
 585                         "when called without a frame");
 586                 return NULL;
 587         }
 588
 589         if (PyDict_GetItemString(globals, "__builtins__") == NULL) {
 590                 if (PyDict_SetItemString(globals, "__builtins__",
 591                                          PyEval_GetBuiltins()) != 0)
 592                         return NULL;
 593         }
 594
 595         if (PyCode_Check(cmd)) {
 596                 if (PyCode_GetNumFree((PyCodeObject *)cmd) > 0) {
 597                         PyErr_SetString(PyExc_TypeError,
 598                 "code object passed to eval() may not contain free variables");
 599                         return NULL;
 600                 }
 601                 return PyEval_EvalCode((PyCodeObject *) cmd, globals, locals);
 602         }
 603
 604         if (!PyString_Check(cmd) &&
 605             !PyUnicode_Check(cmd)) {
 606                 PyErr_SetString(PyExc_TypeError,
 607                            "eval() arg 1 must be a string or code object");
 608                 return NULL;
 609         }
 610         cf.cf_flags = 0;
 611
 612 #ifdef Py_USING_UNICODE
 613         if (PyUnicode_Check(cmd)) {
 614                 tmp = PyUnicode_AsUTF8String(cmd);
 615                 if (tmp == NULL)
 616                         return NULL;
 617                 cmd = tmp;
 618                 cf.cf_flags |= PyCF_SOURCE_IS_UTF8;
 619         }
 620 #endif
 621         if (PyString_AsStringAndSize(cmd, &str, NULL)) {
 622                 Py_XDECREF(tmp);
 623                 return NULL;
 624         }
 625         while (*str == ' ' || *str == '\t')
 626                 str++;
 627
 628         (void)PyEval_MergeCompilerFlags(&cf);
 629         result = PyRun_StringFlags(str, Py_eval_input, globals, locals, &cf);
 630         Py_XDECREF(tmp);
 631         return result;
 632 }
 633
 634 PyDoc_STRVAR(eval_doc,
 635 "eval(source[, globals[, locals]]) -> value\n\
 636 \n\
 637 Evaluate the source in the context of globals and locals.\n\
 638 The source may be a string representing a Python expression\n\
 639 or a code object as returned by compile().\n\
 640 The globals must be a dictionary and locals can be any mapping,\n\
 641 defaulting to the current globals and locals.\n\
 642 If only globals is given, locals defaults to it.\n");
 643
 644
 645 static PyObject *
 646 builtin_execfile(PyObject *self, PyObject *args)
 647 {
 648         char *filename;
 649         PyObject *globals = Py_None, *locals = Py_None;
 650         PyObject *res;
 651         FILE* fp = NULL;
 652         PyCompilerFlags cf;
 653         int exists;
 654
 655         if (Py_Py3kWarningFlag &&
 656             PyErr_Warn(PyExc_DeprecationWarning,
 657                        "execfile() not supported in 3.x") < 0)
 658                 return NULL;
 659
 660         if (!PyArg_ParseTuple(args, "s|O!O:execfile",
 661                         &filename,
 662                         &PyDict_Type, &globals,
 663                         &locals))
 664                 return NULL;
 665         if (locals != Py_None && !PyMapping_Check(locals)) {
 666                 PyErr_SetString(PyExc_TypeError, "locals must be a mapping");
 667                 return NULL;
 668         }
 669         if (globals == Py_None) {
 670                 globals = PyEval_GetGlobals();
 671                 if (locals == Py_None)
 672                         locals = PyEval_GetLocals();
 673         }
 674         else if (locals == Py_None)
 675                 locals = globals;
 676         if (PyDict_GetItemString(globals, "__builtins__") == NULL) {
 677                 if (PyDict_SetItemString(globals, "__builtins__",
 678                                          PyEval_GetBuiltins()) != 0)
 679                         return NULL;
 680         }
 681
 682         exists = 0;
 683         /* Test for existence or directory. */
 684 #if defined(PLAN9)
 685         {
 686                 Dir *d;
 687
 688                 if ((d = dirstat(filename))!=nil) {
 689                         if(d->mode & DMDIR)
 690                                 werrstr("is a directory");
 691                         else
 692                                 exists = 1;
 693                         free(d);
 694                 }
 695         }
 696 #elif defined(RISCOS)
 697         if (object_exists(filename)) {
 698                 if (isdir(filename))
 699                         errno = EISDIR;
 700                 else
 701                         exists = 1;
 702         }
 703 #else   /* standard Posix */
 704         {
 705                 struct stat s;
 706                 if (stat(filename, &s) == 0) {
 707                         if (S_ISDIR(s.st_mode))
 708 #                               if defined(PYOS_OS2) && defined(PYCC_VACPP)
 709                                         errno = EOS2ERR;
 710 #                               else
 711                                         errno = EISDIR;
 712 #                               endif
 713                         else
 714                                 exists = 1;
 715                 }
 716         }
 717 #endif
 718
 719         if (exists) {
 720                 Py_BEGIN_ALLOW_THREADS
 721                 fp = fopen(filename, "r" PY_STDIOTEXTMODE);
 722                 Py_END_ALLOW_THREADS
 723
 724                 if (fp == NULL) {
 725                         exists = 0;
 726                 }
 727         }
 728
 729         if (!exists) {
 730                 PyErr_SetFromErrnoWithFilename(PyExc_IOError, filename);
 731                 return NULL;
 732         }
 733         cf.cf_flags = 0;
 734         if (PyEval_MergeCompilerFlags(&cf))
 735                 res = PyRun_FileExFlags(fp, filename, Py_file_input, globals,
 736                                    locals, 1, &cf);
 737         else
 738                 res = PyRun_FileEx(fp, filename, Py_file_input, globals,
 739                                    locals, 1);
 740         return res;
 741 }
 742
 743 PyDoc_STRVAR(execfile_doc,
 744 "execfile(filename[, globals[, locals]])\n\
 745 \n\
 746 Read and execute a Python script from a file.\n\
 747 The globals and locals are dictionaries, defaulting to the current\n\
 748 globals and locals.  If only globals is given, locals defaults to it.");
 749
 750
 751 static PyObject *
 752 builtin_getattr(PyObject *self, PyObject *args)
 753 {
 754         PyObject *v, *result, *dflt = NULL;
 755         PyObject *name;
 756
 757         if (!PyArg_UnpackTuple(args, "getattr", 2, 3, &v, &name, &dflt))
 758                 return NULL;
 759 #ifdef Py_USING_UNICODE
 760         if (PyUnicode_Check(name)) {
 761                 name = _PyUnicode_AsDefaultEncodedString(name, NULL);
 762                 if (name == NULL)
 763                         return NULL;
 764         }
 765 #endif
 766
 767         if (!PyString_Check(name)) {
 768                 PyErr_SetString(PyExc_TypeError,
 769                                 "getattr(): attribute name must be string");
 770                 return NULL;
 771         }
 772         result = PyObject_GetAttr(v, name);
 773         if (result == NULL && dflt != NULL &&
 774             PyErr_ExceptionMatches(PyExc_AttributeError))
 775         {
 776                 PyErr_Clear();
 777                 Py_INCREF(dflt);
 778                 result = dflt;
 779         }
 780         return result;
 781 }
 782
 783 PyDoc_STRVAR(getattr_doc,
 784 "getattr(object, name[, default]) -> value\n\
 785 \n\
 786 Get a named attribute from an object; getattr(x, 'y') is equivalent to x.y.\n\
 787 When a default argument is given, it is returned when the attribute doesn't\n\
 788 exist; without it, an exception is raised in that case.");
 789
 790
 791 static PyObject *
 792 builtin_globals(PyObject *self)
 793 {
 794         PyObject *d;
 795
 796         d = PyEval_GetGlobals();
 797         Py_XINCREF(d);
 798         return d;
 799 }
 800
 801 PyDoc_STRVAR(globals_doc,
 802 "globals() -> dictionary\n\
 803 \n\
 804 Return the dictionary containing the current scope's global variables.");
 805
 806
 807 static PyObject *
 808 builtin_hasattr(PyObject *self, PyObject *args)
 809 {
 810         PyObject *v;
 811         PyObject *name;
 812
 813         if (!PyArg_UnpackTuple(args, "hasattr", 2, 2, &v, &name))
 814                 return NULL;
 815 #ifdef Py_USING_UNICODE
 816         if (PyUnicode_Check(name)) {
 817                 name = _PyUnicode_AsDefaultEncodedString(name, NULL);
 818                 if (name == NULL)
 819                         return NULL;
 820         }
 821 #endif
 822
 823         if (!PyString_Check(name)) {
 824                 PyErr_SetString(PyExc_TypeError,
 825                                 "hasattr(): attribute name must be string");
 826                 return NULL;
 827         }
 828         v = PyObject_GetAttr(v, name);
 829         if (v == NULL) {
 830                 PyErr_Clear();
 831                 Py_INCREF(Py_False);
 832                 return Py_False;
 833         }
 834         Py_DECREF(v);
 835         Py_INCREF(Py_True);
 836         return Py_True;
 837 }
 838
 839 PyDoc_STRVAR(hasattr_doc,
 840 "hasattr(object, name) -> bool\n\
 841 \n\
 842 Return whether the object has an attribute with the given name.\n\
 843 (This is done by calling getattr(object, name) and catching exceptions.)");
 844
 845
 846 static PyObject *
 847 builtin_id(PyObject *self, PyObject *v)
 848 {
 849         return PyLong_FromVoidPtr(v);
 850 }
 851
 852 PyDoc_STRVAR(id_doc,
 853 "id(object) -> integer\n\
 854 \n\
 855 Return the identity of an object.  This is guaranteed to be unique among\n\
 856 simultaneously existing objects.  (Hint: it's the object's memory address.)");
 857
 858
 859 static PyObject *
 860 builtin_map(PyObject *self, PyObject *args)
 861 {
 862         typedef struct {
 863                 PyObject *it;   /* the iterator object */
 864                 int saw_StopIteration;  /* bool:  did the iterator end? */
 865         } sequence;
 866
 867         PyObject *func, *result;
 868         sequence *seqs = NULL, *sqp;
 869         Py_ssize_t n, len;
 870         register int i, j;
 871
 872         n = PyTuple_Size(args);
 873         if (n < 2) {
 874                 PyErr_SetString(PyExc_TypeError,
 875                                 "map() requires at least two args");
 876                 return NULL;
 877         }
 878
 879         func = PyTuple_GetItem(args, 0);
 880         n--;
 881
 882         if (func == Py_None && n == 1) {
 883                 /* map(None, S) is the same as list(S). */
 884                 return PySequence_List(PyTuple_GetItem(args, 1));
 885         }
 886
 887         /* Get space for sequence descriptors.  Must NULL out the iterator
 888          * pointers so that jumping to Fail_2 later doesn't see trash.
 889          */
 890         if ((seqs = PyMem_NEW(sequence, n)) == NULL) {
 891                 PyErr_NoMemory();
 892                 return NULL;
 893         }
 894         for (i = 0; i < n; ++i) {
 895                 seqs[i].it = (PyObject*)NULL;
 896                 seqs[i].saw_StopIteration = 0;
 897         }
 898
 899         /* Do a first pass to obtain iterators for the arguments, and set len
 900          * to the largest of their lengths.
 901          */
 902         len = 0;
 903         for (i = 0, sqp = seqs; i < n; ++i, ++sqp) {
 904                 PyObject *curseq;
 905                 Py_ssize_t curlen;
 906
 907                 /* Get iterator. */
 908                 curseq = PyTuple_GetItem(args, i+1);
 909                 sqp->it = PyObject_GetIter(curseq);
 910                 if (sqp->it == NULL) {
 911                         static char errmsg[] =
 912                             "argument %d to map() must support iteration";
 913                         char errbuf[sizeof(errmsg) + 25];
 914                         PyOS_snprintf(errbuf, sizeof(errbuf), errmsg, i+2);
 915                         PyErr_SetString(PyExc_TypeError, errbuf);
 916                         goto Fail_2;
 917                 }
 918
 919                 /* Update len. */
 920                 curlen = _PyObject_LengthHint(curseq, 8);
 921                 if (curlen > len)
 922                         len = curlen;
 923         }
 924
 925         /* Get space for the result list. */
 926         if ((result = (PyObject *) PyList_New(len)) == NULL)
 927                 goto Fail_2;
 928
 929         /* Iterate over the sequences until all have stopped. */
 930         for (i = 0; ; ++i) {
 931                 PyObject *alist, *item=NULL, *value;
 932                 int numactive = 0;
 933
 934                 if (func == Py_None && n == 1)
 935                         alist = NULL;
 936                 else if ((alist = PyTuple_New(n)) == NULL)
 937                         goto Fail_1;
 938
 939                 for (j = 0, sqp = seqs; j < n; ++j, ++sqp) {
 940                         if (sqp->saw_StopIteration) {
 941                                 Py_INCREF(Py_None);
 942                                 item = Py_None;
 943                         }
 944                         else {
 945                                 item = PyIter_Next(sqp->it);
 946                                 if (item)
 947                                         ++numactive;
 948                                 else {
 949                                         if (PyErr_Occurred()) {
 950                                                 Py_XDECREF(alist);
 951                                                 goto Fail_1;
 952                                         }
 953                                         Py_INCREF(Py_None);
 954                                         item = Py_None;
 955                                         sqp->saw_StopIteration = 1;
 956                                 }
 957                         }
 958                         if (alist)
 959                                 PyTuple_SET_ITEM(alist, j, item);
 960                         else
 961                                 break;
 962                 }
 963
 964                 if (!alist)
 965                         alist = item;
 966
 967                 if (numactive == 0) {
 968                         Py_DECREF(alist);
 969                         break;
 970                 }
 971
 972                 if (func == Py_None)
 973                         value = alist;
 974                 else {
 975                         value = PyEval_CallObject(func, alist);
 976                         Py_DECREF(alist);
 977                         if (value == NULL)
 978                                 goto Fail_1;
 979                 }
 980                 if (i >= len) {
 981                         int status = PyList_Append(result, value);
 982                         Py_DECREF(value);
 983                         if (status < 0)
 984                                 goto Fail_1;
 985                 }
 986                 else if (PyList_SetItem(result, i, value) < 0)
 987                         goto Fail_1;
 988         }
 989
 990         if (i < len && PyList_SetSlice(result, i, len, NULL) < 0)
 991                 goto Fail_1;
 992
 993         goto Succeed;
 994
 995 Fail_1:
 996         Py_DECREF(result);
 997 Fail_2:
 998         result = NULL;
 999 Succeed:
1000         assert(seqs);
1001         for (i = 0; i < n; ++i)
1002                 Py_XDECREF(seqs[i].it);
1003         PyMem_DEL(seqs);
1004         return result;
1005 }
1006
1007 PyDoc_STRVAR(map_doc,
1008 "map(function, sequence[, sequence, ...]) -> list\n\
1009 \n\
1010 Return a list of the results of applying the function to the items of\n\
1011 the argument sequence(s).  If more than one sequence is given, the\n\
1012 function is called with an argument list consisting of the corresponding\n\
1013 item of each sequence, substituting None for missing values when not all\n\
1014 sequences have the same length.  If the function is None, return a list of\n\
1015 the items of the sequence (or a list of tuples if more than one sequence).");
1016
1017
1018 static PyObject *
1019 builtin_setattr(PyObject *self, PyObject *args)
1020 {
1021         PyObject *v;
1022         PyObject *name;
1023         PyObject *value;
1024
1025         if (!PyArg_UnpackTuple(args, "setattr", 3, 3, &v, &name, &value))
1026                 return NULL;
1027         if (PyObject_SetAttr(v, name, value) != 0)
1028                 return NULL;
1029         Py_INCREF(Py_None);
1030         return Py_None;
1031 }
1032
1033 PyDoc_STRVAR(setattr_doc,
1034 "setattr(object, name, value)\n\
1035 \n\
1036 Set a named attribute on an object; setattr(x, 'y', v) is equivalent to\n\
1037 ``x.y = v''.");
1038
1039
1040 static PyObject *
1041 builtin_delattr(PyObject *self, PyObject *args)
1042 {
1043         PyObject *v;
1044         PyObject *name;
1045
1046         if (!PyArg_UnpackTuple(args, "delattr", 2, 2, &v, &name))
1047                 return NULL;
1048         if (PyObject_SetAttr(v, name, (PyObject *)NULL) != 0)
1049                 return NULL;
1050         Py_INCREF(Py_None);
1051         return Py_None;
1052 }
1053
1054 PyDoc_STRVAR(delattr_doc,
1055 "delattr(object, name)\n\
1056 \n\
1057 Delete a named attribute on an object; delattr(x, 'y') is equivalent to\n\
1058 ``del x.y''.");
1059
1060
1061 static PyObject *
1062 builtin_hash(PyObject *self, PyObject *v)
1063 {
1064         long x;
1065
1066         x = PyObject_Hash(v);
1067         if (x == -1)
1068                 return NULL;
1069         return PyInt_FromLong(x);
1070 }
1071
1072 PyDoc_STRVAR(hash_doc,
1073 "hash(object) -> integer\n\
1074 \n\
1075 Return a hash value for the object.  Two objects with the same value have\n\
1076 the same hash value.  The reverse is not necessarily true, but likely.");
1077
1078
1079 static PyObject *
1080 builtin_hex(PyObject *self, PyObject *v)
1081 {
1082         PyNumberMethods *nb;
1083         PyObject *res;
1084
1085         if ((nb = v->ob_type->tp_as_number) == NULL ||
1086             nb->nb_hex == NULL) {
1087                 PyErr_SetString(PyExc_TypeError,
1088                            "hex() argument can't be converted to hex");
1089                 return NULL;
1090         }
1091         res = (*nb->nb_hex)(v);
1092         if (res && !PyString_Check(res)) {
1093                 PyErr_Format(PyExc_TypeError,
1094                              "__hex__ returned non-string (type %.200s)",
1095                              res->ob_type->tp_name);
1096                 Py_DECREF(res);
1097                 return NULL;
1098         }
1099         return res;
1100 }
1101
1102 PyDoc_STRVAR(hex_doc,
1103 "hex(number) -> string\n\
1104 \n\
1105 Return the hexadecimal representation of an integer or long integer.");
1106
1107
1108 static PyObject *builtin_raw_input(PyObject *, PyObject *);
1109
1110 static PyObject *
1111 builtin_input(PyObject *self, PyObject *args)
1112 {
1113         PyObject *line;
1114         char *str;
1115         PyObject *res;
1116         PyObject *globals, *locals;
1117         PyCompilerFlags cf;
1118
1119         line = builtin_raw_input(self, args);
1120         if (line == NULL)
1121                 return line;
1122         if (!PyArg_Parse(line, "s;embedded '\\0' in input line", &str))
1123                 return NULL;
1124         while (*str == ' ' || *str == '\t')
1125                         str++;
1126         globals = PyEval_GetGlobals();
1127         locals = PyEval_GetLocals();
1128         if (PyDict_GetItemString(globals, "__builtins__") == NULL) {
1129                 if (PyDict_SetItemString(globals, "__builtins__",
1130                                          PyEval_GetBuiltins()) != 0)
1131                         return NULL;
1132         }
1133         cf.cf_flags = 0;
1134         PyEval_MergeCompilerFlags(&cf);
1135         res = PyRun_StringFlags(str, Py_eval_input, globals, locals, &cf);
1136         Py_DECREF(line);
1137         return res;
1138 }
1139
1140 PyDoc_STRVAR(input_doc,
1141 "input([prompt]) -> value\n\
1142 \n\
1143 Equivalent to eval(raw_input(prompt)).");
1144
1145
1146 static PyObject *
1147 builtin_intern(PyObject *self, PyObject *args)
1148 {
1149         PyObject *s;
1150         if (!PyArg_ParseTuple(args, "S:intern", &s))
1151                 return NULL;
1152         if (!PyString_CheckExact(s)) {
1153                 PyErr_SetString(PyExc_TypeError,
1154                                 "can't intern subclass of string");
1155                 return NULL;
1156         }
1157         Py_INCREF(s);
1158         PyString_InternInPlace(&s);
1159         return s;
1160 }
1161
1162 PyDoc_STRVAR(intern_doc,
1163 "intern(string) -> string\n\
1164 \n\
1165 ``Intern'' the given string.  This enters the string in the (global)\n\
1166 table of interned strings whose purpose is to speed up dictionary lookups.\n\
1167 Return the string itself or the previously interned string object with the\n\
1168 same value.");
1169
1170
1171 static PyObject *
1172 builtin_iter(PyObject *self, PyObject *args)
1173 {
1174         PyObject *v, *w = NULL;
1175
1176         if (!PyArg_UnpackTuple(args, "iter", 1, 2, &v, &w))
1177                 return NULL;
1178         if (w == NULL)
1179                 return PyObject_GetIter(v);
1180         if (!PyCallable_Check(v)) {
1181                 PyErr_SetString(PyExc_TypeError,
1182                                 "iter(v, w): v must be callable");
1183                 return NULL;
1184         }
1185         return PyCallIter_New(v, w);
1186 }
1187
1188 PyDoc_STRVAR(iter_doc,
1189 "iter(collection) -> iterator\n\
1190 iter(callable, sentinel) -> iterator\n\
1191 \n\
1192 Get an iterator from an object.  In the first form, the argument must\n\
1193 supply its own iterator, or be a sequence.\n\
1194 In the second form, the callable is called until it returns the sentinel.");
1195
1196
1197 static PyObject *
1198 builtin_len(PyObject *self, PyObject *v)
1199 {
1200         Py_ssize_t res;
1201
1202         res = PyObject_Size(v);
1203         if (res < 0 && PyErr_Occurred())
1204                 return NULL;
1205         return PyInt_FromSsize_t(res);
1206 }
1207
1208 PyDoc_STRVAR(len_doc,
1209 "len(object) -> integer\n\
1210 \n\
1211 Return the number of items of a sequence or mapping.");
1212
1213
1214 static PyObject *
1215 builtin_locals(PyObject *self)
1216 {
1217         PyObject *d;
1218
1219         d = PyEval_GetLocals();
1220         Py_XINCREF(d);
1221         return d;
1222 }
1223
1224 PyDoc_STRVAR(locals_doc,
1225 "locals() -> dictionary\n\
1226 \n\
1227 Update and return a dictionary containing the current scope's local variables.");
1228
1229
1230 static PyObject *
1231 min_max(PyObject *args, PyObject *kwds, int op)
1232 {
1233         PyObject *v, *it, *item, *val, *maxitem, *maxval, *keyfunc=NULL;
1234         const char *name = op == Py_LT ? "min" : "max";
1235
1236         if (PyTuple_Size(args) > 1)
1237                 v = args;
1238         else if (!PyArg_UnpackTuple(args, (char *)name, 1, 1, &v))
1239                 return NULL;
1240
1241         if (kwds != NULL && PyDict_Check(kwds) && PyDict_Size(kwds)) {
1242                 keyfunc = PyDict_GetItemString(kwds, "key");
1243                 if (PyDict_Size(kwds)!=1  ||  keyfunc == NULL) {
1244                         PyErr_Format(PyExc_TypeError,
1245                                 "%s() got an unexpected keyword argument", name);
1246                         return NULL;
1247                 }
1248                 Py_INCREF(keyfunc);
1249         }
1250
1251         it = PyObject_GetIter(v);
1252         if (it == NULL) {
1253                 Py_XDECREF(keyfunc);
1254                 return NULL;
1255         }
1256
1257         maxitem = NULL; /* the result */
1258         maxval = NULL;  /* the value associated with the result */
1259         while (( item = PyIter_Next(it) )) {
1260                 /* get the value from the key function */
1261                 if (keyfunc != NULL) {
1262                         val = PyObject_CallFunctionObjArgs(keyfunc, item, NULL);
1263                         if (val == NULL)
1264                                 goto Fail_it_item;
1265                 }
1266                 /* no key function; the value is the item */
1267                 else {
1268                         val = item;
1269                         Py_INCREF(val);
1270                 }
1271
1272                 /* maximum value and item are unset; set them */
1273                 if (maxval == NULL) {
1274                         maxitem = item;
1275                         maxval = val;
1276                 }
1277                 /* maximum value and item are set; update them as necessary */
1278                 else {
1279                         int cmp = PyObject_RichCompareBool(val, maxval, op);
1280                         if (cmp < 0)
1281                                 goto Fail_it_item_and_val;
1282                         else if (cmp > 0) {
1283                                 Py_DECREF(maxval);
1284                                 Py_DECREF(maxitem);
1285                                 maxval = val;
1286                                 maxitem = item;
1287                         }
1288                         else {
1289                                 Py_DECREF(item);
1290                                 Py_DECREF(val);
1291                         }
1292                 }
1293         }
1294         if (PyErr_Occurred())
1295                 goto Fail_it;
1296         if (maxval == NULL) {
1297                 PyErr_Format(PyExc_ValueError,
1298                              "%s() arg is an empty sequence", name);
1299                 assert(maxitem == NULL);
1300         }
1301         else
1302                 Py_DECREF(maxval);
1303         Py_DECREF(it);
1304         Py_XDECREF(keyfunc);
1305         return maxitem;
1306
1307 Fail_it_item_and_val:
1308         Py_DECREF(val);
1309 Fail_it_item:
1310         Py_DECREF(item);
1311 Fail_it:
1312         Py_XDECREF(maxval);
1313         Py_XDECREF(maxitem);
1314         Py_DECREF(it);
1315         Py_XDECREF(keyfunc);
1316         return NULL;
1317 }
1318
1319 static PyObject *
1320 builtin_min(PyObject *self, PyObject *args, PyObject *kwds)
1321 {
1322         return min_max(args, kwds, Py_LT);
1323 }
1324
1325 PyDoc_STRVAR(min_doc,
1326 "min(iterable[, key=func]) -> value\n\
1327 min(a, b, c, ...[, key=func]) -> value\n\
1328 \n\
1329 With a single iterable argument, return its smallest item.\n\
1330 With two or more arguments, return the smallest argument.");
1331
1332
1333 static PyObject *
1334 builtin_max(PyObject *self, PyObject *args, PyObject *kwds)
1335 {
1336         return min_max(args, kwds, Py_GT);
1337 }
1338
1339 PyDoc_STRVAR(max_doc,
1340 "max(iterable[, key=func]) -> value\n\
1341 max(a, b, c, ...[, key=func]) -> value\n\
1342 \n\
1343 With a single iterable argument, return its largest item.\n\
1344 With two or more arguments, return the largest argument.");
1345
1346
1347 static PyObject *
1348 builtin_oct(PyObject *self, PyObject *v)
1349 {
1350         PyNumberMethods *nb;
1351         PyObject *res;
1352
1353         if (v == NULL || (nb = v->ob_type->tp_as_number) == NULL ||
1354             nb->nb_oct == NULL) {
1355                 PyErr_SetString(PyExc_TypeError,
1356                            "oct() argument can't be converted to oct");
1357                 return NULL;
1358         }
1359         res = (*nb->nb_oct)(v);
1360         if (res && !PyString_Check(res)) {
1361                 PyErr_Format(PyExc_TypeError,
1362                              "__oct__ returned non-string (type %.200s)",
1363                              res->ob_type->tp_name);
1364                 Py_DECREF(res);
1365                 return NULL;
1366         }
1367         return res;
1368 }
1369
1370 PyDoc_STRVAR(oct_doc,
1371 "oct(number) -> string\n\
1372 \n\
1373 Return the octal representation of an integer or long integer.");
1374
1375
1376 static PyObject *
1377 builtin_open(PyObject *self, PyObject *args, PyObject *kwds)
1378 {
1379         return PyObject_Call((PyObject*)&PyFile_Type, args, kwds);
1380 }
1381
1382 PyDoc_STRVAR(open_doc,
1383 "open(name[, mode[, buffering]]) -> file object\n\
1384 \n\
1385 Open a file using the file() type, returns a file object.  This is the\n\
1386 preferred way to open a file.");
1387
1388
1389 static PyObject *
1390 builtin_ord(PyObject *self, PyObject* obj)
1391 {
1392         long ord;
1393         Py_ssize_t size;
1394
1395         if (PyString_Check(obj)) {
1396                 size = PyString_GET_SIZE(obj);
1397                 if (size == 1) {
1398                         ord = (long)((unsigned char)*PyString_AS_STRING(obj));
1399                         return PyInt_FromLong(ord);
1400                 }
1401 #ifdef Py_USING_UNICODE
1402         } else if (PyUnicode_Check(obj)) {
1403                 size = PyUnicode_GET_SIZE(obj);
1404                 if (size == 1) {
1405                         ord = (long)*PyUnicode_AS_UNICODE(obj);
1406                         return PyInt_FromLong(ord);
1407                 }
1408 #endif
1409         } else {
1410                 PyErr_Format(PyExc_TypeError,
1411                              "ord() expected string of length 1, but " \
1412                              "%.200s found", obj->ob_type->tp_name);
1413                 return NULL;
1414         }
1415
1416         PyErr_Format(PyExc_TypeError,
1417                      "ord() expected a character, "
1418                      "but string of length %zd found",
1419                      size);
1420         return NULL;
1421 }
1422
1423 PyDoc_STRVAR(ord_doc,
1424 "ord(c) -> integer\n\
1425 \n\
1426 Return the integer ordinal of a one-character string.");
1427
1428
1429 static PyObject *
1430 builtin_pow(PyObject *self, PyObject *args)
1431 {
1432         PyObject *v, *w, *z = Py_None;
1433
1434         if (!PyArg_UnpackTuple(args, "pow", 2, 3, &v, &w, &z))
1435                 return NULL;
1436         return PyNumber_Power(v, w, z);
1437 }
1438
1439 PyDoc_STRVAR(pow_doc,
1440 "pow(x, y[, z]) -> number\n\
1441 \n\
1442 With two arguments, equivalent to x**y.  With three arguments,\n\
1443 equivalent to (x**y) % z, but may be more efficient (e.g. for longs).");
1444
1445
1446
1447 /* Return number of items in range (lo, hi, step), when arguments are
1448  * PyInt or PyLong objects.  step > 0 required.  Return a value < 0 if
1449  * & only if the true value is too large to fit in a signed long.
1450  * Arguments MUST return 1 with either PyInt_Check() or
1451  * PyLong_Check().  Return -1 when there is an error.
1452  */
1453 static long
1454 get_len_of_range_longs(PyObject *lo, PyObject *hi, PyObject *step)
1455 {
1456         /* -------------------------------------------------------------
1457         Algorithm is equal to that of get_len_of_range(), but it operates
1458         on PyObjects (which are assumed to be PyLong or PyInt objects).
1459         ---------------------------------------------------------------*/
1460         long n;
1461         PyObject *diff = NULL;
1462         PyObject *one = NULL;
1463         PyObject *tmp1 = NULL, *tmp2 = NULL, *tmp3 = NULL;
1464                 /* holds sub-expression evaluations */
1465
1466         /* if (lo >= hi), return length of 0. */
1467         if (PyObject_Compare(lo, hi) >= 0)
1468                 return 0;
1469
1470         if ((one = PyLong_FromLong(1L)) == NULL)
1471                 goto Fail;
1472
1473         if ((tmp1 = PyNumber_Subtract(hi, lo)) == NULL)
1474                 goto Fail;
1475
1476         if ((diff = PyNumber_Subtract(tmp1, one)) == NULL)
1477                 goto Fail;
1478
1479         if ((tmp2 = PyNumber_FloorDivide(diff, step)) == NULL)
1480                 goto Fail;
1481
1482         if ((tmp3 = PyNumber_Add(tmp2, one)) == NULL)
1483                 goto Fail;
1484
1485         n = PyLong_AsLong(tmp3);
1486         if (PyErr_Occurred()) {  /* Check for Overflow */
1487                 PyErr_Clear();
1488                 goto Fail;
1489         }
1490
1491         Py_DECREF(tmp3);
1492         Py_DECREF(tmp2);
1493         Py_DECREF(diff);
1494         Py_DECREF(tmp1);
1495         Py_DECREF(one);
1496         return n;
1497
1498   Fail:
1499         Py_XDECREF(tmp3);
1500         Py_XDECREF(tmp2);
1501         Py_XDECREF(diff);
1502         Py_XDECREF(tmp1);
1503         Py_XDECREF(one);
1504         return -1;
1505 }
1506
1507 /* An extension of builtin_range() that handles the case when PyLong
1508  * arguments are given. */
1509 static PyObject *
1510 handle_range_longs(PyObject *self, PyObject *args)
1511 {
1512         PyObject *ilow;
1513         PyObject *ihigh = NULL;
1514         PyObject *istep = NULL;
1515
1516         PyObject *curnum = NULL;
1517         PyObject *v = NULL;
1518         long bign;
1519         int i, n;
1520         int cmp_result;
1521
1522         PyObject *zero = PyLong_FromLong(0);
1523
1524         if (zero == NULL)
1525                 return NULL;
1526
1527         if (!PyArg_UnpackTuple(args, "range", 1, 3, &ilow, &ihigh, &istep)) {
1528                 Py_DECREF(zero);
1529                 return NULL;
1530         }
1531
1532         /* Figure out which way we were called, supply defaults, and be
1533          * sure to incref everything so that the decrefs at the end
1534          * are correct.
1535          */
1536         assert(ilow != NULL);
1537         if (ihigh == NULL) {
1538                 /* only 1 arg -- it's the upper limit */
1539                 ihigh = ilow;
1540                 ilow = NULL;
1541         }
1542         assert(ihigh != NULL);
1543         Py_INCREF(ihigh);
1544
1545         /* ihigh correct now; do ilow */
1546         if (ilow == NULL)
1547                 ilow = zero;
1548         Py_INCREF(ilow);
1549
1550         /* ilow and ihigh correct now; do istep */
1551         if (istep == NULL) {
1552                 istep = PyLong_FromLong(1L);
1553                 if (istep == NULL)
1554                         goto Fail;
1555         }
1556         else {
1557                 Py_INCREF(istep);
1558         }
1559
1560         if (!PyInt_Check(ilow) && !PyLong_Check(ilow)) {
1561                 PyErr_Format(PyExc_TypeError,
1562                              "range() integer start argument expected, got %s.",
1563                              ilow->ob_type->tp_name);
1564                 goto Fail;
1565         }
1566
1567         if (!PyInt_Check(ihigh) && !PyLong_Check(ihigh)) {
1568                 PyErr_Format(PyExc_TypeError,
1569                              "range() integer end argument expected, got %s.",
1570                              ihigh->ob_type->tp_name);
1571                 goto Fail;
1572         }
1573
1574         if (!PyInt_Check(istep) && !PyLong_Check(istep)) {
1575                 PyErr_Format(PyExc_TypeError,
1576                              "range() integer step argument expected, got %s.",
1577                              istep->ob_type->tp_name);
1578                 goto Fail;
1579         }
1580
1581         if (PyObject_Cmp(istep, zero, &cmp_result) == -1)
1582                 goto Fail;
1583         if (cmp_result == 0) {
1584                 PyErr_SetString(PyExc_ValueError,
1585                                 "range() step argument must not be zero");
1586                 goto Fail;
1587         }
1588
1589         if (cmp_result > 0)
1590                 bign = get_len_of_range_longs(ilow, ihigh, istep);
1591         else {
1592                 PyObject *neg_istep = PyNumber_Negative(istep);
1593                 if (neg_istep == NULL)
1594                         goto Fail;
1595                 bign = get_len_of_range_longs(ihigh, ilow, neg_istep);
1596                 Py_DECREF(neg_istep);
1597         }
1598
1599         n = (int)bign;
1600         if (bign < 0 || (long)n != bign) {
1601                 PyErr_SetString(PyExc_OverflowError,
1602                                 "range() result has too many items");
1603                 goto Fail;
1604         }
1605
1606         v = PyList_New(n);
1607         if (v == NULL)
1608                 goto Fail;
1609
1610         curnum = ilow;
1611         Py_INCREF(curnum);
1612
1613         for (i = 0; i < n; i++) {
1614                 PyObject *w = PyNumber_Long(curnum);
1615                 PyObject *tmp_num;
1616                 if (w == NULL)
1617                         goto Fail;
1618
1619                 PyList_SET_ITEM(v, i, w);
1620
1621                 tmp_num = PyNumber_Add(curnum, istep);
1622                 if (tmp_num == NULL)
1623                         goto Fail;
1624
1625                 Py_DECREF(curnum);
1626                 curnum = tmp_num;
1627         }
1628         Py_DECREF(ilow);
1629         Py_DECREF(ihigh);
1630         Py_DECREF(istep);
1631         Py_DECREF(zero);
1632         Py_DECREF(curnum);
1633         return v;
1634
1635   Fail:
1636         Py_DECREF(ilow);
1637         Py_DECREF(ihigh);
1638         Py_XDECREF(istep);
1639         Py_DECREF(zero);
1640         Py_XDECREF(curnum);
1641         Py_XDECREF(v);
1642         return NULL;
1643 }
1644
1645 /* Return number of items in range/xrange (lo, hi, step).  step > 0
1646  * required.  Return a value < 0 if & only if the true value is too
1647  * large to fit in a signed long.
1648  */
1649 static long
1650 get_len_of_range(long lo, long hi, long step)
1651 {
1652         /* -------------------------------------------------------------
1653         If lo >= hi, the range is empty.
1654         Else if n values are in the range, the last one is
1655         lo + (n-1)*step, which must be <= hi-1.  Rearranging,
1656         n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
1657         the proper value.  Since lo < hi in this case, hi-lo-1 >= 0, so
1658         the RHS is non-negative and so truncation is the same as the
1659         floor.  Letting M be the largest positive long, the worst case
1660         for the RHS numerator is hi=M, lo=-M-1, and then
1661         hi-lo-1 = M-(-M-1)-1 = 2*M.  Therefore unsigned long has enough
1662         precision to compute the RHS exactly.
1663         ---------------------------------------------------------------*/
1664         long n = 0;
1665         if (lo < hi) {
1666                 unsigned long uhi = (unsigned long)hi;
1667                 unsigned long ulo = (unsigned long)lo;
1668                 unsigned long diff = uhi - ulo - 1;
1669                 n = (long)(diff / (unsigned long)step + 1);
1670         }
1671         return n;
1672 }
1673
1674 static PyObject *
1675 builtin_range(PyObject *self, PyObject *args)
1676 {
1677         long ilow = 0, ihigh = 0, istep = 1;
1678         long bign;
1679         int i, n;
1680
1681         PyObject *v;
1682
1683         if (PyTuple_Size(args) <= 1) {
1684                 if (!PyArg_ParseTuple(args,
1685                                 "l;range() requires 1-3 int arguments",
1686                                 &ihigh)) {
1687                         PyErr_Clear();
1688                         return handle_range_longs(self, args);
1689                 }
1690         }
1691         else {
1692                 if (!PyArg_ParseTuple(args,
1693                                 "ll|l;range() requires 1-3 int arguments",
1694                                 &ilow, &ihigh, &istep)) {
1695                         PyErr_Clear();
1696                         return handle_range_longs(self, args);
1697                 }
1698         }
1699         if (istep == 0) {
1700                 PyErr_SetString(PyExc_ValueError,
1701                                 "range() step argument must not be zero");
1702                 return NULL;
1703         }
1704         if (istep > 0)
1705                 bign = get_len_of_range(ilow, ihigh, istep);
1706         else
1707                 bign = get_len_of_range(ihigh, ilow, -istep);
1708         n = (int)bign;
1709         if (bign < 0 || (long)n != bign) {
1710                 PyErr_SetString(PyExc_OverflowError,
1711                                 "range() result has too many items");
1712                 return NULL;
1713         }
1714         v = PyList_New(n);
1715         if (v == NULL)
1716                 return NULL;
1717         for (i = 0; i < n; i++) {
1718                 PyObject *w = PyInt_FromLong(ilow);
1719                 if (w == NULL) {
1720                         Py_DECREF(v);
1721                         return NULL;
1722                 }
1723                 PyList_SET_ITEM(v, i, w);
1724                 ilow += istep;
1725         }
1726         return v;
1727 }
1728
1729 PyDoc_STRVAR(range_doc,
1730 "range([start,] stop[, step]) -> list of integers\n\
1731 \n\
1732 Return a list containing an arithmetic progression of integers.\n\
1733 range(i, j) returns [i, i+1, i+2, ..., j-1]; start (!) defaults to 0.\n\
1734 When step is given, it specifies the increment (or decrement).\n\
1735 For example, range(4) returns [0, 1, 2, 3].  The end point is omitted!\n\
1736 These are exactly the valid indices for a list of 4 elements.");
1737
1738
1739 static PyObject *
1740 builtin_raw_input(PyObject *self, PyObject *args)
1741 {
1742         PyObject *v = NULL;
1743         PyObject *fin = PySys_GetObject("stdin");
1744         PyObject *fout = PySys_GetObject("stdout");
1745
1746         if (!PyArg_UnpackTuple(args, "[raw_]input", 0, 1, &v))
1747                 return NULL;
1748
1749         if (fin == NULL) {
1750                 PyErr_SetString(PyExc_RuntimeError, "[raw_]input: lost sys.stdin");
1751                 return NULL;
1752         }
1753         if (fout == NULL) {
1754                 PyErr_SetString(PyExc_RuntimeError, "[raw_]input: lost sys.stdout");
1755                 return NULL;
1756         }
1757         if (PyFile_SoftSpace(fout, 0)) {
1758                 if (PyFile_WriteString(" ", fout) != 0)
1759                         return NULL;
1760         }
1761         if (PyFile_AsFile(fin) && PyFile_AsFile(fout)
1762             && isatty(fileno(PyFile_AsFile(fin)))
1763             && isatty(fileno(PyFile_AsFile(fout)))) {
1764                 PyObject *po;
1765                 char *prompt;
1766                 char *s;
1767                 PyObject *result;
1768                 if (v != NULL) {
1769                         po = PyObject_Str(v);
1770                         if (po == NULL)
1771                                 return NULL;
1772                         prompt = PyString_AsString(po);
1773                         if (prompt == NULL)
1774                                 return NULL;
1775                 }
1776                 else {
1777                         po = NULL;
1778                         prompt = "";
1779                 }
1780                 s = PyOS_Readline(PyFile_AsFile(fin), PyFile_AsFile(fout),
1781                                   prompt);
1782                 Py_XDECREF(po);
1783                 if (s == NULL) {
1784                         if (!PyErr_Occurred())
1785                                 PyErr_SetNone(PyExc_KeyboardInterrupt);
1786                         return NULL;
1787                 }
1788                 if (*s == '\0') {
1789                         PyErr_SetNone(PyExc_EOFError);
1790                         result = NULL;
1791                 }
1792                 else { /* strip trailing '\n' */
1793                         size_t len = strlen(s);
1794                         if (len > PY_SSIZE_T_MAX) {
1795                                 PyErr_SetString(PyExc_OverflowError,
1796                                                 "[raw_]input: input too long");
1797                                 result = NULL;
1798                         }
1799                         else {
1800                                 result = PyString_FromStringAndSize(s, len-1);
1801                         }
1802                 }
1803                 PyMem_FREE(s);
1804                 return result;
1805         }
1806         if (v != NULL) {
1807                 if (PyFile_WriteObject(v, fout, Py_PRINT_RAW) != 0)
1808                         return NULL;
1809         }
1810         return PyFile_GetLine(fin, -1);
1811 }
1812
1813 PyDoc_STRVAR(raw_input_doc,
1814 "raw_input([prompt]) -> string\n\
1815 \n\
1816 Read a string from standard input.  The trailing newline is stripped.\n\
1817 If the user hits EOF (Unix: Ctl-D, Windows: Ctl-Z+Return), raise EOFError.\n\
1818 On Unix, GNU readline is used if enabled.  The prompt string, if given,\n\
1819 is printed without a trailing newline before reading.");
1820
1821
1822 static PyObject *
1823 builtin_reduce(PyObject *self, PyObject *args)
1824 {
1825         PyObject *seq, *func, *result = NULL, *it;
1826
1827         if (Py_Py3kWarningFlag &&
1828             PyErr_Warn(PyExc_DeprecationWarning,
1829                        "reduce() not supported in 3.x") < 0)
1830                 return NULL;
1831
1832         if (!PyArg_UnpackTuple(args, "reduce", 2, 3, &func, &seq, &result))
1833                 return NULL;
1834         if (result != NULL)
1835                 Py_INCREF(result);
1836
1837         it = PyObject_GetIter(seq);
1838         if (it == NULL) {
1839                 PyErr_SetString(PyExc_TypeError,
1840                     "reduce() arg 2 must support iteration");
1841                 Py_XDECREF(result);
1842                 return NULL;
1843         }
1844
1845         if ((args = PyTuple_New(2)) == NULL)
1846                 goto Fail;
1847
1848         for (;;) {
1849                 PyObject *op2;
1850
1851                 if (args->ob_refcnt > 1) {
1852                         Py_DECREF(args);
1853                         if ((args = PyTuple_New(2)) == NULL)
1854                                 goto Fail;
1855                 }
1856
1857                 op2 = PyIter_Next(it);
1858                 if (op2 == NULL) {
1859                         if (PyErr_Occurred())
1860                                 goto Fail;
1861                         break;
1862                 }
1863
1864                 if (result == NULL)
1865                         result = op2;
1866                 else {
1867                         PyTuple_SetItem(args, 0, result);
1868                         PyTuple_SetItem(args, 1, op2);
1869                         if ((result = PyEval_CallObject(func, args)) == NULL)
1870                                 goto Fail;
1871                 }
1872         }
1873
1874         Py_DECREF(args);
1875
1876         if (result == NULL)
1877                 PyErr_SetString(PyExc_TypeError,
1878                            "reduce() of empty sequence with no initial value");
1879
1880         Py_DECREF(it);
1881         return result;
1882
1883 Fail:
1884         Py_XDECREF(args);
1885         Py_XDECREF(result);
1886         Py_DECREF(it);
1887         return NULL;
1888 }
1889
1890 PyDoc_STRVAR(reduce_doc,
1891 "reduce(function, sequence[, initial]) -> value\n\
1892 \n\
1893 Apply a function of two arguments cumulatively to the items of a sequence,\n\
1894 from left to right, so as to reduce the sequence to a single value.\n\
1895 For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates\n\
1896 ((((1+2)+3)+4)+5).  If initial is present, it is placed before the items\n\
1897 of the sequence in the calculation, and serves as a default when the\n\
1898 sequence is empty.");
1899
1900
1901 static PyObject *
1902 builtin_reload(PyObject *self, PyObject *v)
1903 {
1904         if (Py_Py3kWarningFlag &&
1905             PyErr_Warn(PyExc_DeprecationWarning,
1906                        "reload() not supported in 3.x") < 0)
1907                 return NULL;
1908
1909         return PyImport_ReloadModule(v);
1910 }
1911
1912 PyDoc_STRVAR(reload_doc,
1913 "reload(module) -> module\n\
1914 \n\
1915 Reload the module.  The module must have been successfully imported before.");
1916
1917
1918 static PyObject *
1919 builtin_repr(PyObject *self, PyObject *v)
1920 {
1921         return PyObject_Repr(v);
1922 }
1923
1924 PyDoc_STRVAR(repr_doc,
1925 "repr(object) -> string\n\
1926 \n\
1927 Return the canonical string representation of the object.\n\
1928 For most object types, eval(repr(object)) == object.");
1929
1930
1931 static PyObject *
1932 builtin_round(PyObject *self, PyObject *args, PyObject *kwds)
1933 {
1934         double number;
1935         double f;
1936         int ndigits = 0;
1937         int i;
1938         static char *kwlist[] = {"number", "ndigits", 0};
1939
1940         if (!PyArg_ParseTupleAndKeywords(args, kwds, "d|i:round",
1941                 kwlist, &number, &ndigits))
1942                 return NULL;
1943         f = 1.0;
1944         i = abs(ndigits);
1945         while  (--i >= 0)
1946                 f = f*10.0;
1947         if (ndigits < 0)
1948                 number /= f;
1949         else
1950                 number *= f;
1951         if (number >= 0.0)
1952                 number = floor(number + 0.5);
1953         else
1954                 number = ceil(number - 0.5);
1955         if (ndigits < 0)
1956                 number *= f;
1957         else
1958                 number /= f;
1959         return PyFloat_FromDouble(number);
1960 }
1961
1962 PyDoc_STRVAR(round_doc,
1963 "round(number[, ndigits]) -> floating point number\n\
1964 \n\
1965 Round a number to a given precision in decimal digits (default 0 digits).\n\
1966 This always returns a floating point number.  Precision may be negative.");
1967
1968 static PyObject *
1969 builtin_sorted(PyObject *self, PyObject *args, PyObject *kwds)
1970 {
1971         PyObject *newlist, *v, *seq, *compare=NULL, *keyfunc=NULL, *newargs;
1972         PyObject *callable;
1973         static char *kwlist[] = {"iterable", "cmp", "key", "reverse", 0};
1974         int reverse;
1975
1976         /* args 1-4 should match listsort in Objects/listobject.c */
1977         if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|OOi:sorted",
1978                 kwlist, &seq, &compare, &keyfunc, &reverse))
1979                 return NULL;
1980
1981         newlist = PySequence_List(seq);
1982         if (newlist == NULL)
1983                 return NULL;
1984
1985         callable = PyObject_GetAttrString(newlist, "sort");
1986         if (callable == NULL) {
1987                 Py_DECREF(newlist);
1988                 return NULL;
1989         }
1990
1991         newargs = PyTuple_GetSlice(args, 1, 4);
1992         if (newargs == NULL) {
1993                 Py_DECREF(newlist);
1994                 Py_DECREF(callable);
1995                 return NULL;
1996         }
1997
1998         v = PyObject_Call(callable, newargs, kwds);
1999         Py_DECREF(newargs);
2000         Py_DECREF(callable);
2001         if (v == NULL) {
2002                 Py_DECREF(newlist);
2003                 return NULL;
2004         }
2005         Py_DECREF(v);
2006         return newlist;
2007 }
2008
2009 PyDoc_STRVAR(sorted_doc,
2010 "sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list");
2011
2012 static PyObject *
2013 builtin_vars(PyObject *self, PyObject *args)
2014 {
2015         PyObject *v = NULL;
2016         PyObject *d;
2017
2018         if (!PyArg_UnpackTuple(args, "vars", 0, 1, &v))
2019                 return NULL;
2020         if (v == NULL) {
2021                 d = PyEval_GetLocals();
2022                 if (d == NULL) {
2023                         if (!PyErr_Occurred())
2024                                 PyErr_SetString(PyExc_SystemError,
2025                                                 "vars(): no locals!?");
2026                 }
2027                 else
2028                         Py_INCREF(d);
2029         }
2030         else {
2031                 d = PyObject_GetAttrString(v, "__dict__");
2032                 if (d == NULL) {
2033                         PyErr_SetString(PyExc_TypeError,
2034                             "vars() argument must have __dict__ attribute");
2035                         return NULL;
2036                 }
2037         }
2038         return d;
2039 }
2040
2041 PyDoc_STRVAR(vars_doc,
2042 "vars([object]) -> dictionary\n\
2043 \n\
2044 Without arguments, equivalent to locals().\n\
2045 With an argument, equivalent to object.__dict__.");
2046
2047
2048 static PyObject*
2049 builtin_sum(PyObject *self, PyObject *args)
2050 {
2051         PyObject *seq;
2052         PyObject *result = NULL;
2053         PyObject *temp, *item, *iter;
2054
2055         if (!PyArg_UnpackTuple(args, "sum", 1, 2, &seq, &result))
2056                 return NULL;
2057
2058         iter = PyObject_GetIter(seq);
2059         if (iter == NULL)
2060                 return NULL;
2061
2062         if (result == NULL) {
2063                 result = PyInt_FromLong(0);
2064                 if (result == NULL) {
2065                         Py_DECREF(iter);
2066                         return NULL;
2067                 }
2068         } else {
2069                 /* reject string values for 'start' parameter */
2070                 if (PyObject_TypeCheck(result, &PyBaseString_Type)) {
2071                         PyErr_SetString(PyExc_TypeError,
2072                                 "sum() can't sum strings [use ''.join(seq) instead]");
2073                         Py_DECREF(iter);
2074                         return NULL;
2075                 }
2076                 Py_INCREF(result);
2077         }
2078
2079 #ifndef SLOW_SUM
2080         /* Fast addition by keeping temporary sums in C instead of new Python objects.
2081            Assumes all inputs are the same type.  If the assumption fails, default
2082            to the more general routine.
2083         */
2084         if (PyInt_CheckExact(result)) {
2085                 long i_result = PyInt_AS_LONG(result);
2086                 Py_DECREF(result);
2087                 result = NULL;
2088                 while(result == NULL) {
2089                         item = PyIter_Next(iter);
2090                         if (item == NULL) {
2091                                 Py_DECREF(iter);
2092                                 if (PyErr_Occurred())
2093                                         return NULL;
2094                                 return PyInt_FromLong(i_result);
2095                         }
2096                         if (PyInt_CheckExact(item)) {
2097                                 long b = PyInt_AS_LONG(item);
2098                                 long x = i_result + b;
2099                                 if ((x^i_result) >= 0 || (x^b) >= 0) {
2100                                         i_result = x;
2101                                         Py_DECREF(item);
2102                                         continue;
2103                                 }
2104                         }
2105                         /* Either overflowed or is not an int. Restore real objects and process normally */
2106                         result = PyInt_FromLong(i_result);
2107                         temp = PyNumber_Add(result, item);
2108                         Py_DECREF(result);
2109                         Py_DECREF(item);
2110                         result = temp;
2111                         if (result == NULL) {
2112                                 Py_DECREF(iter);
2113                                 return NULL;
2114                         }
2115                 }
2116         }
2117
2118         if (PyFloat_CheckExact(result)) {
2119                 double f_result = PyFloat_AS_DOUBLE(result);
2120                 Py_DECREF(result);
2121                 result = NULL;
2122                 while(result == NULL) {
2123                         item = PyIter_Next(iter);
2124                         if (item == NULL) {
2125                                 Py_DECREF(iter);
2126                                 if (PyErr_Occurred())
2127                                         return NULL;
2128                                 return PyFloat_FromDouble(f_result);
2129                         }
2130                         if (PyFloat_CheckExact(item)) {
2131                                 PyFPE_START_PROTECT("add", return 0)
2132                                 f_result += PyFloat_AS_DOUBLE(item);
2133                                 PyFPE_END_PROTECT(f_result)
2134                                 Py_DECREF(item);
2135                                 continue;
2136                         }
2137                         if (PyInt_CheckExact(item)) {
2138                                 PyFPE_START_PROTECT("add", return 0)
2139                                 f_result += (double)PyInt_AS_LONG(item);
2140                                 PyFPE_END_PROTECT(f_result)
2141                                 Py_DECREF(item);
2142                                 continue;
2143                         }
2144                         result = PyFloat_FromDouble(f_result);
2145                         temp = PyNumber_Add(result, item);
2146                         Py_DECREF(result);
2147                         Py_DECREF(item);
2148                         result = temp;
2149                         if (result == NULL) {
2150                                 Py_DECREF(iter);
2151                                 return NULL;
2152                         }
2153                 }
2154         }
2155 #endif
2156
2157         for(;;) {
2158                 item = PyIter_Next(iter);
2159                 if (item == NULL) {
2160                         /* error, or end-of-sequence */
2161                         if (PyErr_Occurred()) {
2162                                 Py_DECREF(result);
2163                                 result = NULL;
2164                         }
2165                         break;
2166                 }
2167                 temp = PyNumber_Add(result, item);
2168                 Py_DECREF(result);
2169                 Py_DECREF(item);
2170                 result = temp;
2171                 if (result == NULL)
2172                         break;
2173         }
2174         Py_DECREF(iter);
2175         return result;
2176 }
2177
2178 PyDoc_STRVAR(sum_doc,
2179 "sum(sequence[, start]) -> value\n\
2180 \n\
2181 Returns the sum of a sequence of numbers (NOT strings) plus the value\n\
2182 of parameter 'start' (which defaults to 0).  When the sequence is\n\
2183 empty, returns start.");
2184
2185
2186 static PyObject *
2187 builtin_isinstance(PyObject *self, PyObject *args)
2188 {
2189         PyObject *inst;
2190         PyObject *cls;
2191         int retval;
2192
2193         if (!PyArg_UnpackTuple(args, "isinstance", 2, 2, &inst, &cls))
2194                 return NULL;
2195
2196         retval = PyObject_IsInstance(inst, cls);
2197         if (retval < 0)
2198                 return NULL;
2199         return PyBool_FromLong(retval);
2200 }
2201
2202 PyDoc_STRVAR(isinstance_doc,
2203 "isinstance(object, class-or-type-or-tuple) -> bool\n\
2204 \n\
2205 Return whether an object is an instance of a class or of a subclass thereof.\n\
2206 With a type as second argument, return whether that is the object's type.\n\
2207 The form using a tuple, isinstance(x, (A, B, ...)), is a shortcut for\n\
2208 isinstance(x, A) or isinstance(x, B) or ... (etc.).");
2209
2210
2211 static PyObject *
2212 builtin_issubclass(PyObject *self, PyObject *args)
2213 {
2214         PyObject *derived;
2215         PyObject *cls;
2216         int retval;
2217
2218         if (!PyArg_UnpackTuple(args, "issubclass", 2, 2, &derived, &cls))
2219                 return NULL;
2220
2221         retval = PyObject_IsSubclass(derived, cls);
2222         if (retval < 0)
2223                 return NULL;
2224         return PyBool_FromLong(retval);
2225 }
2226
2227 PyDoc_STRVAR(issubclass_doc,
2228 "issubclass(C, B) -> bool\n\
2229 \n\
2230 Return whether class C is a subclass (i.e., a derived class) of class B.\n\
2231 When using a tuple as the second argument issubclass(X, (A, B, ...)),\n\
2232 is a shortcut for issubclass(X, A) or issubclass(X, B) or ... (etc.).");
2233
2234
2235 static PyObject*
2236 builtin_zip(PyObject *self, PyObject *args)
2237 {
2238         PyObject *ret;
2239         const Py_ssize_t itemsize = PySequence_Length(args);
2240         Py_ssize_t i;
2241         PyObject *itlist;  /* tuple of iterators */
2242         Py_ssize_t len;    /* guess at result length */
2243
2244         if (itemsize == 0)
2245                 return PyList_New(0);
2246
2247         /* args must be a tuple */
2248         assert(PyTuple_Check(args));
2249
2250         /* Guess at result length:  the shortest of the input lengths.
2251            If some argument refuses to say, we refuse to guess too, lest
2252            an argument like xrange(sys.maxint) lead us astray.*/
2253         len = -1;       /* unknown */
2254         for (i = 0; i < itemsize; ++i) {
2255                 PyObject *item = PyTuple_GET_ITEM(args, i);
2256                 Py_ssize_t thislen = _PyObject_LengthHint(item, -1);
2257                 if (thislen < 0) {
2258                         len = -1;
2259                         break;
2260                 }
2261                 else if (len < 0 || thislen < len)
2262                         len = thislen;
2263         }
2264
2265         /* allocate result list */
2266         if (len < 0)
2267                 len = 10;       /* arbitrary */
2268         if ((ret = PyList_New(len)) == NULL)
2269                 return NULL;
2270
2271         /* obtain iterators */
2272         itlist = PyTuple_New(itemsize);
2273         if (itlist == NULL)
2274                 goto Fail_ret;
2275         for (i = 0; i < itemsize; ++i) {
2276                 PyObject *item = PyTuple_GET_ITEM(args, i);
2277                 PyObject *it = PyObject_GetIter(item);
2278                 if (it == NULL) {
2279                         if (PyErr_ExceptionMatches(PyExc_TypeError))
2280                                 PyErr_Format(PyExc_TypeError,
2281                                     "zip argument #%zd must support iteration",
2282                                     i+1);
2283                         goto Fail_ret_itlist;
2284                 }
2285                 PyTuple_SET_ITEM(itlist, i, it);
2286         }
2287
2288         /* build result into ret list */
2289         for (i = 0; ; ++i) {
2290                 int j;
2291                 PyObject *next = PyTuple_New(itemsize);
2292                 if (!next)
2293                         goto Fail_ret_itlist;
2294
2295                 for (j = 0; j < itemsize; j++) {
2296                         PyObject *it = PyTuple_GET_ITEM(itlist, j);
2297                         PyObject *item = PyIter_Next(it);
2298                         if (!item) {
2299                                 if (PyErr_Occurred()) {
2300                                         Py_DECREF(ret);
2301                                         ret = NULL;
2302                                 }
2303                                 Py_DECREF(next);
2304                                 Py_DECREF(itlist);
2305                                 goto Done;
2306                         }
2307                         PyTuple_SET_ITEM(next, j, item);
2308                 }
2309
2310                 if (i < len)
2311                         PyList_SET_ITEM(ret, i, next);
2312                 else {
2313                         int status = PyList_Append(ret, next);
2314                         Py_DECREF(next);
2315                         ++len;
2316                         if (status < 0)
2317                                 goto Fail_ret_itlist;
2318                 }
2319         }
2320
2321 Done:
2322         if (ret != NULL && i < len) {
2323                 /* The list is too big. */
2324                 if (PyList_SetSlice(ret, i, len, NULL) < 0)
2325                         return NULL;
2326         }
2327         return ret;
2328
2329 Fail_ret_itlist:
2330         Py_DECREF(itlist);
2331 Fail_ret:
2332         Py_DECREF(ret);
2333         return NULL;
2334 }
2335
2336
2337 PyDoc_STRVAR(zip_doc,
2338 "zip(seq1 [, seq2 [...]]) -> [(seq1[0], seq2[0] ...), (...)]\n\
2339 \n\
2340 Return a list of tuples, where each tuple contains the i-th element\n\
2341 from each of the argument sequences.  The returned list is truncated\n\
2342 in length to the length of the shortest argument sequence.");
2343
2344
2345 static PyMethodDef builtin_methods[] = {
2346         {"__import__",  (PyCFunction)builtin___import__, METH_VARARGS | METH_KEYWORDS, import_doc},
2347         {"abs",         builtin_abs,        METH_O, abs_doc},
2348         {"all",         builtin_all,        METH_O, all_doc},
2349         {"any",         builtin_any,        METH_O, any_doc},
2350         {"apply",       builtin_apply,      METH_VARARGS, apply_doc},
2351         {"callable",    builtin_callable,   METH_O, callable_doc},
2352         {"chr",         builtin_chr,        METH_VARARGS, chr_doc},
2353         {"cmp",         builtin_cmp,        METH_VARARGS, cmp_doc},
2354         {"coerce",      builtin_coerce,     METH_VARARGS, coerce_doc},
2355         {"compile",     (PyCFunction)builtin_compile,    METH_VARARGS | METH_KEYWORDS, compile_doc},
2356         {"delattr",     builtin_delattr,    METH_VARARGS, delattr_doc},
2357         {"dir",         builtin_dir,        METH_VARARGS, dir_doc},
2358         {"divmod",      builtin_divmod,     METH_VARARGS, divmod_doc},
2359         {"eval",        builtin_eval,       METH_VARARGS, eval_doc},
2360         {"execfile",    builtin_execfile,   METH_VARARGS, execfile_doc},
2361         {"filter",      builtin_filter,     METH_VARARGS, filter_doc},
2362         {"getattr",     builtin_getattr,    METH_VARARGS, getattr_doc},
2363         {"globals",     (PyCFunction)builtin_globals,    METH_NOARGS, globals_doc},
2364         {"hasattr",     builtin_hasattr,    METH_VARARGS, hasattr_doc},
2365         {"hash",        builtin_hash,       METH_O, hash_doc},
2366         {"hex",         builtin_hex,        METH_O, hex_doc},
2367         {"id",          builtin_id,         METH_O, id_doc},
2368         {"input",       builtin_input,      METH_VARARGS, input_doc},
2369         {"intern",      builtin_intern,     METH_VARARGS, intern_doc},
2370         {"isinstance",  builtin_isinstance, METH_VARARGS, isinstance_doc},
2371         {"issubclass",  builtin_issubclass, METH_VARARGS, issubclass_doc},
2372         {"iter",        builtin_iter,       METH_VARARGS, iter_doc},
2373         {"len",         builtin_len,        METH_O, len_doc},
2374         {"locals",      (PyCFunction)builtin_locals,     METH_NOARGS, locals_doc},
2375         {"map",         builtin_map,        METH_VARARGS, map_doc},
2376         {"max",         (PyCFunction)builtin_max,        METH_VARARGS | METH_KEYWORDS, max_doc},
2377         {"min",         (PyCFunction)builtin_min,        METH_VARARGS | METH_KEYWORDS, min_doc},
2378         {"oct",         builtin_oct,        METH_O, oct_doc},
2379         {"open",        (PyCFunction)builtin_open,       METH_VARARGS | METH_KEYWORDS, open_doc},
2380         {"ord",         builtin_ord,        METH_O, ord_doc},
2381         {"pow",         builtin_pow,        METH_VARARGS, pow_doc},
2382         {"range",       builtin_range,      METH_VARARGS, range_doc},
2383         {"raw_input",   builtin_raw_input,  METH_VARARGS, raw_input_doc},
2384         {"reduce",      builtin_reduce,     METH_VARARGS, reduce_doc},
2385         {"reload",      builtin_reload,     METH_O, reload_doc},
2386         {"repr",        builtin_repr,       METH_O, repr_doc},
2387         {"round",       (PyCFunction)builtin_round,      METH_VARARGS | METH_KEYWORDS, round_doc},
2388         {"setattr",     builtin_setattr,    METH_VARARGS, setattr_doc},
2389         {"sorted",      (PyCFunction)builtin_sorted,     METH_VARARGS | METH_KEYWORDS, sorted_doc},
2390         {"sum",         builtin_sum,        METH_VARARGS, sum_doc},
2391 #ifdef Py_USING_UNICODE
2392         {"unichr",      builtin_unichr,     METH_VARARGS, unichr_doc},
2393 #endif
2394         {"vars",        builtin_vars,       METH_VARARGS, vars_doc},
2395         {"zip",         builtin_zip,        METH_VARARGS, zip_doc},
2396         {NULL,          NULL},
2397 };
2398
2399 PyDoc_STRVAR(builtin_doc,
2400 "Built-in functions, exceptions, and other objects.\n\
2401 \n\
2402 Noteworthy: None is the `nil' object; Ellipsis represents `...' in slices.");
2403
2404 PyObject *
2405 _PyBuiltin_Init(void)
2406 {
2407         PyObject *mod, *dict, *debug;
2408         mod = Py_InitModule4("__builtin__", builtin_methods,
2409                              builtin_doc, (PyObject *)NULL,
2410                              PYTHON_API_VERSION);
2411         if (mod == NULL)
2412                 return NULL;
2413         dict = PyModule_GetDict(mod);
2414
2415 #ifdef Py_TRACE_REFS
2416         /* __builtin__ exposes a number of statically allocated objects
2417          * that, before this code was added in 2.3, never showed up in
2418          * the list of "all objects" maintained by Py_TRACE_REFS.  As a
2419          * result, programs leaking references to None and False (etc)
2420          * couldn't be diagnosed by examining sys.getobjects(0).
2421          */
2422 #define ADD_TO_ALL(OBJECT) _Py_AddToAllObjects((PyObject *)(OBJECT), 0)
2423 #else
2424 #define ADD_TO_ALL(OBJECT) (void)0
2425 #endif
2426
2427 #define SETBUILTIN(NAME, OBJECT) \
2428         if (PyDict_SetItemString(dict, NAME, (PyObject *)OBJECT) < 0)   \
2429                 return NULL;                                            \
2430         ADD_TO_ALL(OBJECT)
2431
2432         SETBUILTIN("None",              Py_None);
2433         SETBUILTIN("Ellipsis",          Py_Ellipsis);
2434         SETBUILTIN("NotImplemented",    Py_NotImplemented);
2435         SETBUILTIN("False",             Py_False);
2436         SETBUILTIN("True",              Py_True);
2437         SETBUILTIN("basestring",        &PyBaseString_Type);
2438         SETBUILTIN("bool",              &PyBool_Type);
2439         SETBUILTIN("bytes",             &PyString_Type);
2440         SETBUILTIN("buffer",            &PyBuffer_Type);
2441         SETBUILTIN("classmethod",       &PyClassMethod_Type);
2442 #ifndef WITHOUT_COMPLEX
2443         SETBUILTIN("complex",           &PyComplex_Type);
2444 #endif
2445         SETBUILTIN("dict",              &PyDict_Type);
2446         SETBUILTIN("enumerate",         &PyEnum_Type);
2447         SETBUILTIN("file",              &PyFile_Type);
2448         SETBUILTIN("float",             &PyFloat_Type);
2449         SETBUILTIN("frozenset",         &PyFrozenSet_Type);
2450         SETBUILTIN("property",          &PyProperty_Type);
2451         SETBUILTIN("int",               &PyInt_Type);
2452         SETBUILTIN("list",              &PyList_Type);
2453         SETBUILTIN("long",              &PyLong_Type);
2454         SETBUILTIN("object",            &PyBaseObject_Type);
2455         SETBUILTIN("reversed",          &PyReversed_Type);
2456         SETBUILTIN("set",               &PySet_Type);
2457         SETBUILTIN("slice",             &PySlice_Type);
2458         SETBUILTIN("staticmethod",      &PyStaticMethod_Type);
2459         SETBUILTIN("str",               &PyString_Type);
2460         SETBUILTIN("super",             &PySuper_Type);
2461         SETBUILTIN("tuple",             &PyTuple_Type);
2462         SETBUILTIN("type",              &PyType_Type);
2463         SETBUILTIN("xrange",            &PyRange_Type);
2464 #ifdef Py_USING_UNICODE
2465         SETBUILTIN("unicode",           &PyUnicode_Type);
2466 #endif
2467         debug = PyBool_FromLong(Py_OptimizeFlag == 0);
2468         if (PyDict_SetItemString(dict, "__debug__", debug) < 0) {
2469                 Py_XDECREF(debug);
2470                 return NULL;
2471         }
2472         Py_XDECREF(debug);
2473
2474         return mod;
2475 #undef ADD_TO_ALL
2476 #undef SETBUILTIN
2477 }
2478
2479 /* Helper for filter(): filter a tuple through a function */
2480
2481 static PyObject *
2482 filtertuple(PyObject *func, PyObject *tuple)
2483 {
2484         PyObject *result;
2485         Py_ssize_t i, j;
2486         Py_ssize_t len = PyTuple_Size(tuple);
2487
2488         if (len == 0) {
2489                 if (PyTuple_CheckExact(tuple))
2490                         Py_INCREF(tuple);
2491                 else
2492                         tuple = PyTuple_New(0);
2493                 return tuple;
2494         }
2495
2496         if ((result = PyTuple_New(len)) == NULL)
2497                 return NULL;
2498
2499         for (i = j = 0; i < len; ++i) {
2500                 PyObject *item, *good;
2501                 int ok;
2502
2503                 if (tuple->ob_type->tp_as_sequence &&
2504                     tuple->ob_type->tp_as_sequence->sq_item) {
2505                         item = tuple->ob_type->tp_as_sequence->sq_item(tuple, i);
2506                         if (item == NULL)
2507                                 goto Fail_1;
2508                 } else {
2509                         PyErr_SetString(PyExc_TypeError, "filter(): unsubscriptable tuple");
2510                         goto Fail_1;
2511                 }
2512                 if (func == Py_None) {
2513                         Py_INCREF(item);
2514                         good = item;
2515                 }
2516                 else {
2517                         PyObject *arg = PyTuple_Pack(1, item);
2518                         if (arg == NULL) {
2519                                 Py_DECREF(item);
2520                                 goto Fail_1;
2521                         }
2522                         good = PyEval_CallObject(func, arg);
2523                         Py_DECREF(arg);
2524                         if (good == NULL) {
2525                                 Py_DECREF(item);
2526                                 goto Fail_1;
2527                         }
2528                 }
2529                 ok = PyObject_IsTrue(good);
2530                 Py_DECREF(good);
2531                 if (ok) {
2532                         if (PyTuple_SetItem(result, j++, item) < 0)
2533                                 goto Fail_1;
2534                 }
2535                 else
2536                         Py_DECREF(item);
2537         }
2538
2539         if (_PyTuple_Resize(&result, j) < 0)
2540                 return NULL;
2541
2542         return result;
2543
2544 Fail_1:
2545         Py_DECREF(result);
2546         return NULL;
2547 }
2548
2549
2550 /* Helper for filter(): filter a string through a function */
2551
2552 static PyObject *
2553 filterstring(PyObject *func, PyObject *strobj)
2554 {
2555         PyObject *result;
2556         Py_ssize_t i, j;
2557         Py_ssize_t len = PyString_Size(strobj);
2558         Py_ssize_t outlen = len;
2559
2560         if (func == Py_None) {
2561                 /* If it's a real string we can return the original,
2562                  * as no character is ever false and __getitem__
2563                  * does return this character. If it's a subclass
2564                  * we must go through the __getitem__ loop */
2565                 if (PyString_CheckExact(strobj)) {
2566                         Py_INCREF(strobj);
2567                         return strobj;
2568                 }
2569         }
2570         if ((result = PyString_FromStringAndSize(NULL, len)) == NULL)
2571                 return NULL;
2572
2573         for (i = j = 0; i < len; ++i) {
2574                 PyObject *item;
2575                 int ok;
2576
2577                 item = (*strobj->ob_type->tp_as_sequence->sq_item)(strobj, i);
2578                 if (item == NULL)
2579                         goto Fail_1;
2580                 if (func==Py_None) {
2581                         ok = 1;
2582                 } else {
2583                         PyObject *arg, *good;
2584                         arg = PyTuple_Pack(1, item);
2585                         if (arg == NULL) {
2586                                 Py_DECREF(item);
2587                                 goto Fail_1;
2588                         }
2589                         good = PyEval_CallObject(func, arg);
2590                         Py_DECREF(arg);
2591                         if (good == NULL) {
2592                                 Py_DECREF(item);
2593                                 goto Fail_1;
2594                         }
2595                         ok = PyObject_IsTrue(good);
2596                         Py_DECREF(good);
2597                 }
2598                 if (ok) {
2599                         Py_ssize_t reslen;
2600                         if (!PyString_Check(item)) {
2601                                 PyErr_SetString(PyExc_TypeError, "can't filter str to str:"
2602                                         " __getitem__ returned different type");
2603                                 Py_DECREF(item);
2604                                 goto Fail_1;
2605                         }
2606                         reslen = PyString_GET_SIZE(item);
2607                         if (reslen == 1) {
2608                                 PyString_AS_STRING(result)[j++] =
2609                                         PyString_AS_STRING(item)[0];
2610                         } else {
2611                                 /* do we need more space? */
2612                                 Py_ssize_t need = j + reslen + len-i-1;
2613                                 if (need > outlen) {
2614                                         /* overallocate, to avoid reallocations */
2615                                         if (need<2*outlen)
2616                                                 need = 2*outlen;
2617                                         if (_PyString_Resize(&result, need)) {
2618                                                 Py_DECREF(item);
2619                                                 return NULL;
2620                                         }
2621                                         outlen = need;
2622                                 }
2623                                 memcpy(
2624                                         PyString_AS_STRING(result) + j,
2625                                         PyString_AS_STRING(item),
2626                                         reslen
2627                                 );
2628                                 j += reslen;
2629                         }
2630                 }
2631                 Py_DECREF(item);
2632         }
2633
2634         if (j < outlen)
2635                 _PyString_Resize(&result, j);
2636
2637         return result;
2638
2639 Fail_1:
2640         Py_DECREF(result);
2641         return NULL;
2642 }
2643
2644 #ifdef Py_USING_UNICODE
2645 /* Helper for filter(): filter a Unicode object through a function */
2646
2647 static PyObject *
2648 filterunicode(PyObject *func, PyObject *strobj)
2649 {
2650         PyObject *result;
2651         register Py_ssize_t i, j;
2652         Py_ssize_t len = PyUnicode_GetSize(strobj);
2653         Py_ssize_t outlen = len;
2654
2655         if (func == Py_None) {
2656                 /* If it's a real string we can return the original,
2657                  * as no character is ever false and __getitem__
2658                  * does return this character. If it's a subclass
2659                  * we must go through the __getitem__ loop */
2660                 if (PyUnicode_CheckExact(strobj)) {
2661                         Py_INCREF(strobj);
2662                         return strobj;
2663                 }
2664         }
2665         if ((result = PyUnicode_FromUnicode(NULL, len)) == NULL)
2666                 return NULL;
2667
2668         for (i = j = 0; i < len; ++i) {
2669                 PyObject *item, *arg, *good;
2670                 int ok;
2671
2672                 item = (*strobj->ob_type->tp_as_sequence->sq_item)(strobj, i);
2673                 if (item == NULL)
2674                         goto Fail_1;
2675                 if (func == Py_None) {
2676                         ok = 1;
2677                 } else {
2678                         arg = PyTuple_Pack(1, item);
2679                         if (arg == NULL) {
2680                                 Py_DECREF(item);
2681                                 goto Fail_1;
2682                         }
2683                         good = PyEval_CallObject(func, arg);
2684                         Py_DECREF(arg);
2685                         if (good == NULL) {
2686                                 Py_DECREF(item);
2687                                 goto Fail_1;
2688                         }
2689                         ok = PyObject_IsTrue(good);
2690                         Py_DECREF(good);
2691                 }
2692                 if (ok) {
2693                         Py_ssize_t reslen;
2694                         if (!PyUnicode_Check(item)) {
2695                                 PyErr_SetString(PyExc_TypeError,
2696                                 "can't filter unicode to unicode:"
2697                                 " __getitem__ returned different type");
2698                                 Py_DECREF(item);
2699                                 goto Fail_1;
2700                         }
2701                         reslen = PyUnicode_GET_SIZE(item);
2702                         if (reslen == 1)
2703                                 PyUnicode_AS_UNICODE(result)[j++] =
2704                                         PyUnicode_AS_UNICODE(item)[0];
2705                         else {
2706                                 /* do we need more space? */
2707                                 Py_ssize_t need = j + reslen + len - i - 1;
2708                                 if (need > outlen) {
2709                                         /* overallocate,
2710                                            to avoid reallocations */
2711                                         if (need < 2 * outlen)
2712                                                 need = 2 * outlen;
2713                                         if (PyUnicode_Resize(
2714                                                 &result, need) < 0) {
2715                                                 Py_DECREF(item);
2716                                                 goto Fail_1;
2717                                         }
2718                                         outlen = need;
2719                                 }
2720                                 memcpy(PyUnicode_AS_UNICODE(result) + j,
2721                                        PyUnicode_AS_UNICODE(item),
2722                                        reslen*sizeof(Py_UNICODE));
2723                                 j += reslen;
2724                         }
2725                 }
2726                 Py_DECREF(item);
2727         }
2728
2729         if (j < outlen)
2730                 PyUnicode_Resize(&result, j);
2731
2732         return result;
2733
2734 Fail_1:
2735         Py_DECREF(result);
2736         return NULL;
2737 }
2738 #endif