PEP 234: Iterators

[Michael Hudson]

Just van Rossum <just at letterror.com> writes:

> "Rainer Deyke" <root at rainerdeyke.com> writes:
> 
> [ getting an exception when you modify a dict during iteration ]
> > It would be nice if this could be made reliable.
>
> Michael Hudson wrote:
> 
> > Tricky, that.  It could be made somewhat more reliable, but I think
> > making it totally certain would have prohibitive drawbacks,
> > particularly as stuff like:
> > 
> > for i in d:
> >     d[i] += 1
> > 
> > *is* supported.
> 
> I think you get a RuntimeError if the dictionary gets resized: the dict
> iterator object can check cheaply for that event. 

Yes.

> Perhaps if the dict object grew a magic counter, which would get
> incremented when a new key is added or a key is deleted, and the
> dict iterator would check for *that* value, this would be more
> reliable.

It's not very hard, as it turns out:

Index: dictobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/dictobject.c,v
retrieving revision 2.81
diff -c -1 -r2.81 dictobject.c
*** dictobject.c	2001/05/01 12:10:21	2.81
--- dictobject.c	2001/05/01 22:12:43
***************
*** 103,104 ****
--- 103,105 ----
  	int ma_poly;  /* appopriate entry from polys vector */
+ 	int ma_altercount; /* magic to prevent dict mutation on iteration */
  	dictentry *ma_table;
***************
*** 144,145 ****
--- 145,147 ----
  	mp->ma_used = 0;
+ 	mp->ma_altercount = 0;
  	mp->ma_lookup = lookdict_string;
***************
*** 367,370 ****
  	else {
! 		if (ep->me_key == NULL)
  			mp->ma_fill++;
  		else
--- 369,374 ----
  	else {
! 		if (ep->me_key == NULL) {
  			mp->ma_fill++;
+ 			mp->ma_altercount++;
+ 		}
  		else
***************
*** 547,548 ****
--- 551,553 ----
  		goto empty;
+ 	mp->ma_altercount++;
  	ep = (mp->ma_lookup)(mp, key, hash);
***************
*** 1481,1483 ****
  	dictobject *di_dict;
! 	int di_size;
  	int di_pos;
--- 1486,1488 ----
  	dictobject *di_dict;
! 	int di_altercount;
  	int di_pos;
***************
*** 1495,1497 ****
  	di->di_dict = dict;
! 	di->di_size = dict->ma_size;
  	di->di_pos = 0;
--- 1500,1502 ----
  	di->di_dict = dict;
! 	di->di_altercount = dict->ma_altercount;
  	di->di_pos = 0;
***************
*** 1513,1517 ****
  
! 	if (di->di_size != di->di_dict->ma_size) {
  		PyErr_SetString(PyExc_RuntimeError,
! 				"dictionary changed size during iteration");
  		return NULL;
--- 1518,1522 ----
  
! 	if (di->di_altercount != di->di_dict->ma_altercount) {
  		PyErr_SetString(PyExc_RuntimeError,
! 				"dictionary altered during iteration");
  		return NULL;

> I can't judge whether this approach would be too expensive or not.

Me neither.  It's at least possible.  I could run a pybench run, but
right now I'm going to bed.

see-you-tomorrow-ly y'rs,
M.

-- 
  "The future" has arrived but they forgot to update the docs.
                                        -- R. David Murray, 9 May 2000