Merged revisions 60481,60485,60489-60492,60494-60496,60498-60499,60501-60503,60505-60506,60508-60509,60523-60524,60532,60543,60545,60547-60548,60552,60554,60556-60559,60561-60562,60569,60571-60572,60574,60576-60583,60585-60586,60589,60591,60594-60595,60597-60598,60600-60601,60606-60612,60615,60617,60619-60621,60623-60625,60627-60629,60631,60633,60635,60647,60650,60652,60654,60656,60658-60659,60664-60666,60668-60670,60672,60676,60678,60680-60683,60685-60686,60688,60690,60692-60694,60697-60700,60705-60706,60708,60711,60714,60720,60724-60730,60732,60736,60742,60744,60746,60748,60750-60751,60753,60756-60757,60759-60761,60763-60764,60766,60769-60770,60774-60784,60787-60789,60793,60796,60799-60809,60812-60813,60815-60821,60823-60826,60828-60829,60831-60834,60836,60838-60839,60846-60849,60852-60854,60856-60859,60861-60870,60874-60875,60880-60881,60886,60888-60890,60892,60894-60898,60900-60931,60933-60958 via svnmerge from

svn+ssh://pythondev@svn.python.org/python/trunk

........
  r60901 | eric.smith | 2008-02-19 14:21:56 +0100 (Tue, 19 Feb 2008) | 1 line

  Added PEP 3101.
........
  r60907 | georg.brandl | 2008-02-20 20:12:36 +0100 (Wed, 20 Feb 2008) | 2 lines

  Fixes contributed by Ori Avtalion.
........
  r60909 | eric.smith | 2008-02-21 00:34:22 +0100 (Thu, 21 Feb 2008) | 1 line

  Trim leading zeros from a floating point exponent, per C99.  See issue 1600.  As far as I know, this only affects Windows.  Add float type 'n' to PyOS_ascii_formatd (see PEP 3101 for 'n' description).
........
  r60910 | eric.smith | 2008-02-21 00:39:28 +0100 (Thu, 21 Feb 2008) | 1 line

  Now that PyOS_ascii_formatd supports the 'n' format, simplify the float formatting code to just call it.
........
  r60918 | andrew.kuchling | 2008-02-21 15:23:38 +0100 (Thu, 21 Feb 2008) | 2 lines

  Close manifest file.
  This change doesn't make any difference to CPython, but is a necessary fix for Jython.
........
  r60921 | guido.van.rossum | 2008-02-21 18:46:16 +0100 (Thu, 21 Feb 2008) | 2 lines

  Remove news about float repr() -- issue 1580 is still in limbo.
........
  r60923 | guido.van.rossum | 2008-02-21 19:18:37 +0100 (Thu, 21 Feb 2008) | 5 lines

  Removed uses of dict.has_key() from distutils, and uses of
  callable() from copy_reg.py, so the interpreter now starts up
  without warnings when '-3' is given.  More work like this needs to
  be done in the rest of the stdlib.
........
  r60924 | thomas.heller | 2008-02-21 19:28:48 +0100 (Thu, 21 Feb 2008) | 4 lines

  configure.ac: Remove the configure check for _Bool, it is already done in the
  top-level Python configure script.
  configure, fficonfig.h.in: regenerated.
........
  r60925 | thomas.heller | 2008-02-21 19:52:20 +0100 (Thu, 21 Feb 2008) | 3 lines

  Replace 'has_key()' with 'in'.
  Replace 'raise Error, stuff' with 'raise Error(stuff)'.
........
  r60927 | raymond.hettinger | 2008-02-21 20:24:53 +0100 (Thu, 21 Feb 2008) | 1 line

  Update more instances of has_key().
........
  r60928 | guido.van.rossum | 2008-02-21 20:46:35 +0100 (Thu, 21 Feb 2008) | 3 lines

  Fix a few typos and layout glitches (more work is needed).
  Move 2.5 news to Misc/HISTORY.
........
  r60936 | georg.brandl | 2008-02-21 21:33:38 +0100 (Thu, 21 Feb 2008) | 2 lines

  #2079: typo in userdict docs.
........
  r60938 | georg.brandl | 2008-02-21 21:38:13 +0100 (Thu, 21 Feb 2008) | 2 lines

  Part of #2154: minimal syntax fixes in doc example snippets.
........
  r60942 | raymond.hettinger | 2008-02-22 04:16:42 +0100 (Fri, 22 Feb 2008) | 1 line

  First draft for itertools.product().  Docs and other updates forthcoming.
........
  r60955 | nick.coghlan | 2008-02-22 11:54:06 +0100 (Fri, 22 Feb 2008) | 1 line

  Try to make command line error messages from runpy easier to understand (and suppress traceback cruft from the implicitly invoked runpy machinery)
........
  r60956 | georg.brandl | 2008-02-22 13:31:45 +0100 (Fri, 22 Feb 2008) | 2 lines

  A lot more typo fixes by Ori Avtalion.
........
  r60957 | georg.brandl | 2008-02-22 13:56:34 +0100 (Fri, 22 Feb 2008) | 2 lines

  Don't reference pyshell.
........
  r60958 | georg.brandl | 2008-02-22 13:57:05 +0100 (Fri, 22 Feb 2008) | 2 lines

  Another fix.
........

1 files changed, 212 insertions, 1 deletions

diff --git a/Modules/itertoolsmodule.c b/Modules/itertoolsmodule.c
index 9e51663..613515a 100644
--- a/Modules/itertoolsmodule.c
+++ b/Modules/itertoolsmodule.c
@@ -1711,6 +1711,216 @@ static PyTypeObject chain_type = {
 };
 
 
+/* product object ************************************************************/
+
+typedef struct {
+	PyObject_HEAD
+	PyObject *pools;		/* tuple of pool tuples */
+	Py_ssize_t *maxvec;
+	Py_ssize_t *indices;
+	PyObject *result;
+	int stopped;
+} productobject;
+
+static PyTypeObject product_type;
+
+static PyObject *
+product_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
+{
+	productobject *lz;
+	Py_ssize_t npools;
+	PyObject *pools = NULL;
+	Py_ssize_t *maxvec = NULL;
+	Py_ssize_t *indices = NULL;
+	Py_ssize_t i;
+
+	if (type == &product_type && !_PyArg_NoKeywords("product()", kwds))
+		return NULL;
+
+	assert(PyTuple_Check(args));
+	npools = PyTuple_GET_SIZE(args);
+
+	maxvec = PyMem_Malloc(npools * sizeof(Py_ssize_t));
+	indices = PyMem_Malloc(npools * sizeof(Py_ssize_t));
+	if (maxvec == NULL || indices == NULL) {
+    		PyErr_NoMemory();
+		goto error;
+	}
+
+	pools = PyTuple_New(npools);
+	if (pools == NULL)
+		goto error;
+
+	for (i=0; i < npools; ++i) {
+		PyObject *item = PyTuple_GET_ITEM(args, i);
+		PyObject *pool = PySequence_Tuple(item);
+		if (pool == NULL)
+			goto error;
+
+		PyTuple_SET_ITEM(pools, i, pool);
+		maxvec[i] = PyTuple_GET_SIZE(pool);
+		indices[i] = 0;
+	}
+
+	/* create productobject structure */
+	lz = (productobject *)type->tp_alloc(type, 0);
+	if (lz == NULL) {
+		Py_DECREF(pools);
+		return NULL;
+	}
+
+	lz->pools = pools;
+	lz->maxvec = maxvec;
+	lz->indices = indices;
+	lz->result = NULL;
+	lz->stopped = 0;
+
+	return (PyObject *)lz;
+
+error:
+	if (maxvec != NULL)
+		PyMem_Free(maxvec);
+	if (indices != NULL)
+		PyMem_Free(indices);
+	Py_XDECREF(pools);
+	return NULL;
+}
+
+static void
+product_dealloc(productobject *lz)
+{
+	PyObject_GC_UnTrack(lz);
+	Py_XDECREF(lz->pools);
+	Py_XDECREF(lz->result);
+	PyMem_Free(lz->maxvec);
+	PyMem_Free(lz->indices);
+	Py_TYPE(lz)->tp_free(lz);
+}
+
+static int
+product_traverse(productobject *lz, visitproc visit, void *arg)
+{
+	Py_VISIT(lz->pools);
+	Py_VISIT(lz->result);
+	return 0;
+}
+
+static PyObject *
+product_next(productobject *lz)
+{
+	PyObject *pool;
+	PyObject *elem;
+	PyObject *tuple_result;
+	PyObject *pools = lz->pools;
+	PyObject *result = lz->result;
+	Py_ssize_t npools = PyTuple_GET_SIZE(pools);
+	Py_ssize_t i;
+
+	if (lz->stopped)
+		return NULL;
+	if (result == NULL) {
+		if (npools == 0)
+			goto empty;
+		result = PyList_New(npools);
+		if (result == NULL)
+            		goto empty;
+		lz->result = result;
+		for (i=0; i < npools; i++) {
+			pool = PyTuple_GET_ITEM(pools, i);
+			if (PyTuple_GET_SIZE(pool) == 0)
+				goto empty;
+    			elem = PyTuple_GET_ITEM(pool, 0);
+    			Py_INCREF(elem);
+    			PyList_SET_ITEM(result, i, elem);
+		}
+	} else {
+		Py_ssize_t *indices = lz->indices;
+		Py_ssize_t *maxvec = lz->maxvec;
+		for (i=npools-1 ; i >= 0 ; i--) {
+			pool = PyTuple_GET_ITEM(pools, i);
+			indices[i]++;
+			if (indices[i] == maxvec[i]) {
+				indices[i] = 0;
+				elem = PyTuple_GET_ITEM(pool, 0);
+				Py_INCREF(elem);
+				PyList_SetItem(result, i, elem);
+			} else {
+				elem = PyTuple_GET_ITEM(pool, indices[i]);
+				Py_INCREF(elem);
+				PyList_SetItem(result, i, elem);
+				break;
+			}
+		}
+		if (i < 0)
+			return NULL;
+	}
+
+	tuple_result = PySequence_Tuple(result);
+	if (tuple_result == NULL)
+		lz->stopped = 1;
+	return tuple_result;
+
+empty:
+	lz->stopped = 1;
+	return NULL;
+}
+
+PyDoc_STRVAR(product_doc,
+"product(*iterables) --> product object\n\
+\n\
+Cartesian product of input interables.  Equivalent to nested for-loops.\n\n\
+For example, product(A, B) returns the same as:  ((x,y) for x in A for y in B).\n\
+The leftmost iterators are in the outermost for-loop, so the output tuples\n\
+cycle in a manner similar to an odometer (with the rightmost element changing\n\
+on every iteration).\n\n\
+product('ab', range(3)) --> ('a',0) ('a',1) ('a',2) ('b',0) ('b',1) ('b',2)\n\
+product((0,1), (0,1), (0,1)) --> (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) ...");
+
+static PyTypeObject product_type = {
+	PyVarObject_HEAD_INIT(NULL, 0)
+	"itertools.product",		/* tp_name */
+	sizeof(productobject),	/* tp_basicsize */
+	0,				/* tp_itemsize */
+	/* methods */
+	(destructor)product_dealloc,	/* tp_dealloc */
+	0,				/* tp_print */
+	0,				/* tp_getattr */
+	0,				/* tp_setattr */
+	0,				/* tp_compare */
+	0,				/* tp_repr */
+	0,				/* tp_as_number */
+	0,				/* tp_as_sequence */
+	0,				/* tp_as_mapping */
+	0,				/* tp_hash */
+	0,				/* tp_call */
+	0,				/* tp_str */
+	PyObject_GenericGetAttr,	/* tp_getattro */
+	0,				/* tp_setattro */
+	0,				/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+		Py_TPFLAGS_BASETYPE,	/* tp_flags */
+	product_doc,			/* tp_doc */
+	(traverseproc)product_traverse,	/* tp_traverse */
+	0,				/* tp_clear */
+	0,				/* tp_richcompare */
+	0,				/* tp_weaklistoffset */
+	PyObject_SelfIter,		/* tp_iter */
+	(iternextfunc)product_next,	/* tp_iternext */
+	0,				/* tp_methods */
+	0,				/* tp_members */
+	0,				/* tp_getset */
+	0,				/* tp_base */
+	0,				/* tp_dict */
+	0,				/* tp_descr_get */
+	0,				/* tp_descr_set */
+	0,				/* tp_dictoffset */
+	0,				/* tp_init */
+	0,				/* tp_alloc */
+	product_new,			/* tp_new */
+	PyObject_GC_Del,		/* tp_free */
+};
+
+
 /* ifilter object ************************************************************/
 
 typedef struct {
@@ -2748,7 +2958,8 @@ inititertools(void)
 		&ifilterfalse_type,
 		&count_type,
 		&izip_type,
-		&iziplongest_type,                
+		&iziplongest_type,
+		&product_type,          
 		&repeat_type,
 		&groupby_type,
 		NULL