Re: Implementing NSFastEnumeration

On Oct 1, 2009, at 21:49, Christopher Kane wrote:

>
> 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.
>

But my array just does return autoreleased objects, not objects that  
live anywhere in any collection. The example I gave using a dictionary  
was just for illustration, in my real code it essentially returns a  
temporary proxy object for a key-value pair. On the other hand, I  
definitely don't have the situation you sketch, and I control the use  
completely.

But this problem actually reminds me of a similar problem I had with  
PDFOutline in 10.4, which was returning temporary autoreleased  
children, with disastrous consequences. So I understand the predicament.

I guess the only solution to your problem would be somehow to keep the  
returned objects (which could be done lazily), or otherwise only  
return them one at a time?

>
>> 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).

Well, that's not what the docs say (that's the documentation bug I've  
been talking about). If I read the docs I can reach only one  
conclusion: the count returned by this method returns the number of  
items that are returned by reference in stackbuf, and those items are  
iterated over, and therefore there are at most len of them. I know  
this conclusion is wrong. Just read the line after the method name,  
and then the description of stackbuf. This documentation bug really  
needs to be fixed! rdar://problem/7267655.

> 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...)

I can't imagine that could give a problem, because as soon as they may  
become invalid I've already replaced them in stackbuf, while at the  
point I use them they should still be valid.

>
> 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.
>

That's what I said.

>
>> 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.
>

That's what I've done now. I was hoping I could push the advantages of  
fast enumeration a bit further.

>
>> 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
>

That's what I expected. But given the really bad documentation on  
NSFastEnumeration I truly cannot trust that it has been properly  
documented for the collection classes. It wouldn't be the first time  
missing documentation has bit me that way.

thanks
Christiaan