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