Python/bltinmodule.c

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