Re: Implementing NSFastEnumeration

On Oct 1, 2009, at 9:30 AM, Christiaan Hofman wrote:

>
> On Oct 1, 2009, at 17:19, Gerd Knops wrote:
>
>>
>> On Oct 1, 2009, at 8:13 AM, Christiaan Hofman wrote:
>>
>>> I've been reading the documentation on NSFastEnumeration (both the  
>>> docs on the protocol and the section in the Objective-C 2.0  
>>> Programming Language guide). But it is really cryptic and misses  
>>> most of the relevant information to help in implementing it.
>>
>> Below some code I have been using. To access the array to be  
>> enumerated, it uses these methods that my code provides:
>>
>> - (unsigned)version;
>> - (unsigned)countOfChildrenAtVersion:(unsigned)aVersion;
>> - (id)childAtIndex:(unsigned)index forVersion:(unsigned)aVersion;
>>
>> It makes use of the extra array to keep track of the version it is  
>> enumerating, in case it changes while the enumeration goes on. In  
>> my case it is safe to use "self" as the mutationsPtr because the  
>> only way the child array might change is by adding additional  
>> children.
>>
>> Looking at it now I am not sure if the [child retain] part is  
>> correct, might create a memory leak. I'll have to check on that.  
>> And it'll need some changes to be 64-bit safe.
>>
>> But anyway this should get you started.
>>
>> Gerd
>>
>> - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState  
>> *)state
>> 	objects:(id *)stackbuf
>> 	count:(NSUInteger)len
>> {
>> 	
>> 	// typedef struct {
>> 	//    unsigned long state;
>> 	//    id *itemsPtr;
>> 	//    unsigned long *mutationsPtr;
>> 	//    unsigned long extra[5];
>> 	// } NSFastEnumerationState;
>> 	
>> 	unsigned	idx=state->state;
>> 	unsigned	version=(idx>0)?state->extra[0]:[self version];
>> 	unsigned	numChildren=[self countOfChildrenAtVersion:version];
>> 	NSUInteger	now=0;
>> 	
>> 	while(now<len && idx<numChildren)
>> 	{
>> 		id	child=[self childAtIndex:idx forVersion:version];
>> 		
>> 		stackbuf[now++]=[child retain];
>> 		idx++;
>> 	}
>> 	
>> 	state->extra[0]=version;
>> 	state->state=(unsigned long)idx;
>> 	state->itemsPtr=stackbuf;
>> 	state->mutationsPtr=(unsigned long *)self;
>> 	
>> 	return now;
>> }
>>
>
> First of all, thanks for those who replied. From the replies (and  
> also a test I just did) it seems the docs are simply wrong, so I  
> filed a radar against the docs (also asking for real docs instead of  
> the current useless mess).
>
> One problem for me is that the actually returned objects are  
> temporary autoreleased objects. I'm sure your retain is wrong  
> without GC.

Right (on the retain being wrong).  Where is the matching -release?   
Since an NSFastEnumeration adopter does not get any 'notification' of  
the enumeration being done (as when, for example, it is terminated  
early by a 'break' statement in the loop body), you at least have to  
do a retain/autorelease.  But that is going to result in all the  
objects in the collection ending up in the current autorelease pool  
with their lifetimes extended (in addition to the slight cpu perf hit  
to the retain/autorelease).

Back on returning temp autoreleased objects -- you definitely want to  
put those in the stack buffer so they end up in the  
[countByEnumeratingWithState:...] caller's stack frame, so that the  
garbage collector sees them and doesn't nuke them, if you ever switch  
to GC (or you are trying to write code that works either way, as in a  
framework).  The same lifetime/cpu comment as above applies to the  
temp autoreleased objects, of course.

But that isn't the end of the story.  Suppose someone does this:

NSAutoreleasePool *pool = [NSAutoreleasePool new];

for (id obj in myCollection) {
	...
	if (some condition) { // "keep the pool from getting too large",  
perhaps?
		[pool drain]; // -drain == release, not just emptying, so must  
create a new pool:
		pool = [NSAutoreleasePool new];
	}
	...
}

[pool release];

The NSFastEnumeration method is called somewhere around the open curly  
"{" of the loop block above, conceptually, and the loop block is  
invoked potentially many times for each -countByEnumer... call (up to  
however much that protocol method returned as its return value).

Suppose your implementation of -countByEnumer... fills the stackbuf  
with 10 newly created, autoreleased objects and returns 10.  Those  
objects end up in the pool above.  The block begins to be invoked 10  
times... On invocation #4, say, the code above decides to purge the  
current autorelease pool and establish a new one.  That releases and  
possibly frees all 10 objects that you put into the stackbuf, and now  
the invocation of the loop block will continue 6 more times, with  
'obj' being successively assigned 6 pointers to potentially bogus/ 
freed/reused-as-something-else objects.  (Cue dramatic sting music...)

[Did I just hear 9 developers cry out in horror, as they realized  
*they* do this?]

Returning autoreleased objects from the countByEnumer... method is  
just plain asking for trouble, in rare but real cases.



> The other thing is that I want to enumerate the underlying array of  
> keys first. I tried something along these lines:
>
> - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState  
> *)state
> 	objects:(id *)stackbuf
> 	count:(NSUInteger)len
> {
> 	NSUInteger i, count = [keys countByEnumeratingWithState:state  
> objects:stackbuf count:len];
> 	for (i = 0; i < count; i++)
> 	{
> 		id key = state->itemsPtr[i];
> 		id value = [values objectForKey:key];
> 		stackbuf[i] = value;
> 	}
> 	state->itemsPtr = stackbuf;
> 	return count;
> }
>
> While this works for small arrays, for larger arrays this gives a  
> memory access crasher. The reason seems to be that NSArray can  
> return more items than len (the size of stackbuf) in a single call.

The number of returned object pointed to by itemsPtr is, by protocol  
definition, the return value from countByEnumer... and an adopter is  
free to return as many objects as they like (which could also be less  
than the stackbuf length or available number left in the collection).   
And you can't count on (as you are above, slightly*) the other  
NSFastEnumeration adopter NOT using the stackbuf for some effect.  (*  
for example, see comment above about using stackbuf in GC, though I  
can imagine other more nefarious uses, though those might have  
undefined behavior...)

Messing with 'state' yourself, if you're also giving it to another  
object in countByEnumer... is also generally a no-no, I suspect, since  
you can't know what it is doing with it.


> Would there be a way to modify this implementation to work? Or am I  
> forced to get the objects from keys without using fast enumeration  
> (in which case fast enumeration becomes hardly fast)?

I think you need to "enumerate" the array by index and objectAtIndex:,  
saving the "index so far" in one of the extra fields, for the simplest  
solution.  Given the autorelease issue above, I'm not sure it's worth  
considering the possibilities any deeper.


> And another question I have been unable to find an answer to in the  
> docs. Foundation collections are implemented as class clusters. So  
> is NSFastEnumeration implemented as a primitive or a derived method?  
> In other words: when I subclass NSArray (or another collection  
> class), does it already have a default implementation of  
> NSFastEnumeration, or am I forced to always implement it when I want  
> to use for(...in...)?


NSArray has an abstract implementation of - 
countByEnumeratingWithState:..., as do the other Foundation  
collections, and I think if people write their own class clusters  
which adopt NSFastEnumeration they should do the same.  Otherwise  
they're basically adding another primitive method to the cluster which  
has to be implemented by all subclasses.  And an abstract  
implementation should be possible; if not, that suggests there aren't  
enough published primitives.  NSArray's abstract implementation just  
operates in terms of [self objectAtIndex:] for example.  Note that an  
abstract implementation is not necessarily *fast*, it's there to  
permit "out-of-the-box" operability of subclasses with for(in).



Chris Kane
Cocoa Frameworks, Apple