__assoc metatable entry (was Re: GC puzzler...)

[Mark Hamburg <mhamburg@...>]

In http://lua-users.org/lists/lua-l/2005-02/msg00479.html I described a
modification to Lua to work around the problems with semi-weak metatables
for at least the common case of needing a single link from an object to
another object.

To summarize, the idea was to add an __assoc metatable entry. When marking
table or userdata x, the garbage collector would also mark

    getmetatable( x ).__assoc[ x ]

(Assuming all of the steps in the path exist.)

We can protect the metatable for x so that prying eyes can't look inside. We
can make __assoc a fully-weak table. The resulting behavior, however, is as
if __assoc were a weak-keyed table. This is exactly what one wants when
trying to hide implementation objects behind proxy objects.

Unfortunately, further contemplation of the changes I outlined in the e-mail
lead me to conclude that it probably doesn't do the right thing with respect
to the incremental garbage collector.

At the very least, setting the metatable on a black object will need to run
the logic to mark through the __assoc table. That wasn't on my list before.
It's not fundamentally hard, but it does point out the subtleties involved
in implementing thi.

More problematic, however, is the ordering issue. To use this safely, it
would seem one would need to set the entry in the __assoc table for the
proxy and then set the metatable on the proxy. Otherwise, we might miss the
point at which the implementation marks through the __assoc table.
Specifically, if we did:

    local proxy2imp = setmetatable( {}, { __mode = "kv" } )

    local mt = { __assoc = proxy2imp }

    local proxy = { }
    local imp = { }

    setmetatable( proxy, mt )
        -- Assume that the garbage collector now comes along and marks proxy
        -- but not imp. We indirect through the mt.__assoc and find nothing
        -- and hence mark nothing.

    proxy2imp[ proxy ] = imp
        -- Too late. proxy might already be marked and hence we won't mark
        -- through to imp.

The fix for this would be when storing entries in a table, if the key is
already marked, then we should mark the value. That, however, affects a lot
more than any of the changes needed for this extension up to this point.

Mark