Python/bltinmodule.c

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