Re: GC and userdata mark and sweep

[Mark Hamburg <mark@...>]

I concur with the suggestion that you should start by putting the node  
data in userdata and the links in userdata environment tables. This  
will avoid needing to make changes to the GC. Furthermore, if you are  
storing the links between nodes as refs, then they won't get GC'd  
anyway, so changing the GC wasn't going to help you anyway.

What you could do to make traversal fast is store the pointers between  
the data for nodes in the nodes themselves and in the environment  
tables. You could do this as follows:

1. Maintain a global weak-valued table mapping addresses (light  
userdata) to full userdata. This is so that you can easily go from a C  
pointer to the appropriate Lua value. Creating a node then looks  
something like the following. This leaves the userdata for the created  
node on the top of the stack because you don't want it to get GC'd.  
So, don't forget to pop it off when done with initialization and  
linking it in.

(Please excuse any errors. I haven't programmed against the Lua C API  
in a while.)

	void PushNodeMap( lua_State* L ) {
		lua_pushlightuserdata( L, &PushNodeMap );	// Just looking for a  
unique key
		lua_gettable( L, LUA_REGISTRYINDEX );				// Look up the node map
		if( lua_isnil( L, -1 ) ) {
			lua_pop( L, 1 );
			lua_newtable( L );
			lua_newtable( L );						// Metatable
			lua_pushliteral( "v" );
			lua_setfield( L, -2, "__mode" );
			lua_setmetatable( L, -2 );
		}
	}

	Node* CreateNode( lua_State* L ) {
		Node* n = (Node*) lua_newuserdata( L, sizeof( *n ) );
		lua_newtable( L );		// Environment table for node
		lua_setfenv( L, -2 );
		PushNodeMetatable( L );
		lua_setmetatable( L, -2 );
		PushNodeMap( L );
		lua_pushlightuserdata( L, n );
		lua_pushvalue( L, -3 );	// The userdata
		lua_settable( L, -3 );		// nodeMap[ lightud( n ) ] = fullud( n )
		lua_pop( L, 1 );			// Pop nodemap
		return n;
	}

2. When you want to set a link in a node, you need to also set the  
environment table for the node.

	void SetNodeLink( lua_State* L, Node* node, Node** field, Node*  
value ) {
		PushNodeMap( L );
		lua_pushlightuserdata( L, node );
		lua_gettable( L, -2 );		// node as full userdata
		lua_getfenv( L, -1 );		// Get the environment table
		lua_pushlightuserdata( L, field );	// key
		lua_pushlightuserdata( L, value );
		lua_gettable( L, -5);		// value as full userdata
		lua_settable( L, -3 );		// node.env[ field ] = value
		lua_pop( L, 3 );			// Pop map, node, and environment
		*field = value;
	}

Note that a value of NULL works because we won't find anything when we  
do the lookup in the node map.

The above scheme could work perfectly well with polymorphic nodes.

One can imagine optimized versions of the above that get to assume  
we've already put the target node on the stack (e.g, because it's the  
target of a method). If the value wire up is being triggered from Lua,  
we may also have the Lua value already on the stack thereby obviating  
the need for the node map.

If setting links on nodes is rare enough, then one might want to delay  
creating a specialized environment for a node until we actually set  
something in the node.

This actually plays well to a modification that I was looking at  
making to Lua to provide a pseudo-index for the environment table of  
the first item in the stack frame. That's easy enough to write, but  
it's difficult to do in a way that maintains binary compatibility with  
existing compiled C code unless one assumes a limit on upvalues.

Anyway, even without this modification, this gives you code that can  
run entirely natively over the node graph but still relies on the Lua  
GC to manage node lifetimes.

Mark

P.S. Here's a version without the node map in which nodes are expected  
to already exist as Lua references:

Node* CreateNode( lua_State* L ) {
		Node* n = (Node*) lua_newuserdata( L, sizeof( *n ) );
		lua_newtable( L );		// Environment table for node
		lua_setfenv( L, -2 );
		PushNodeMetatable( L );
		lua_setmetatable( L, -2 );
		return n;
}

void SetNodeLink( lua_State* L, int nodeIndex, Node** field, int  
valueIndex ) {
	Node* v = (Node*) lua_touserdata( L, valueIndex );
	if( valueIndex < 0 && -valueIndex <= lua_gettop( L ) )
		valueIndex = lua_gettop( L ) + 1 + valueIndex;
	lua_getfenv( L, nodeIndex );
	lua_pushlightuserdata( L, v );
	lua_pushvalue( L, valueIndex );
	lua_settable( L, -3 );
	lua_pop( L, 1 );
	*field = v;
}