Python-2.7.3/Python/bltinmodule.c

No issues found

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