problem with lists and weak references in pure LUA

[Benoit Germain <bgermain@...>]

Hi all,

I was playing with LUA 5.1w2, and my tests yielded the following thoughts:

#1 It be cool if LUA offered the following information on tables:
- is it currently using array, hash, both or none to store its contents ?
- what is the maximal range of integral values that one can use, even with
holes, to be sure that it won't store a new integral key in a hashed node ?

#2 It be cool if LUA offered to set a 'weak' mode on a per table field
basis. I suppose it would be possible for a hash pair to hold 'weak' bits.
When a table has the 'weak' metatable field, it is ignored during mark
phase, but if not, it is traversed, and again weak bits would be tested for
each pair, with a (negligible ?) performance hit.


For those who want to know the how and why, here it is (the others can skip)

I want to implement a messaging system as a generic inter-module
communication scheme. To do so the principle would be:

* to send a message, get an object from the system and use it:
obj = MessageSystem:GetSenderObject("message name")
reply = obj:SendMessage{ whatever you want, provided the receivers
understand it } -- where reply is the updated original message table

* to receive a message, provide a subscriber 'object' that implements a
predefined messaging interface that will be used when a message is received.
receiver = {}
function receiver:OnMessage(_message)
	...
	return true -- handled, pass to next subscriber in sequence
end
MessageSystem:SubscribeToMessage(receiver,"message name")

All of this would be pretty straightforward if I did not want:
-A priority sorted recipients
-B the ability to discard the receptor without having to unsubscribe it from
the message system

to get -A, I could use equivalence classes (ie an array indexed by integral
priorities, where the values are tables of objects that subscribed to the
message). But this means that I need to enforce a non-sparse small range of
integral priority values, or else I'll end-up with a full-fledged hash table
that decided the indexes were unsuited for pure array storage, which will
defeat the ordering during the traversal. Things (error catching) would be
simpler if the answers to thought #1 were 'yes' and 'yes'

Unfortunately, it's not the case, so I thought about a linked list approach.
But there are problems as well. First, sorted insertion is more expensive
than in the previous approach. But mainly, I can't do -B, because:

(*) For a receptor to be collected, the last strong reference must be held
by the end-user, and not the list(s) it is subscribed to, else it will never
be collected even when the user loses reference to it. Therefore, it must be
referenced by a table (a list node) with a weak value mode (if the key is a
string, for example). But this means that node linking cannot work, because
a node will hold weak references to it's neighbors as well, thus the node
itself will be collected. Or I must reference them as keys, and not values,
which would slow list traversal because I would need to traverse the table
in order to identify who is precedessor and who is successor.

(**) a variant would have a normal weak-valued node, with the receptor
having a strong reference to it. But then, when some receptor is collected,
I end up with a node only weak-referenced by its neighbors (themselves being
strong-referenced by their associated receptors), therefore it will be
collected, thus effectively cutting the list, because no __gc handling will
occur so that it can unlink itself.

(***) When the receptor is collected, no __gc metamethod is called if it is
a table, therefore, it can't be itself a list node, because there is no way
it can unlink itself from the list at that point. And again, to be collected
it must not be strongly referenced by it's neighbors (and it must not
reference them strongly either)... see point (*) above.

With thought #2, all becomes easy: nodes are normal tables strongly
referencing each other, and weakly referencing their payload, thus not
preventing its collection. During list traversal (for example when a message
is sent), any node whose payload is evaluated to nil is silently unlinked,
et voilà :-)



Am I making any sense, or simply a fool of myself ?

__________________________________
Benoit Germain
][ Engineer
+33 4 50 10 93 52
<mailto:bgermain@ubisoft.fr>
__________________________________