Dictionary

After discussing Weak References and Proxies there is only one feature left in that group of odd features that are language and runtime features at the same time: Dictionary.

ActionScript Dictionaries are essentially object (key) to object (value) maps. Since JavaScript only supports string (key) to object (value) maps we have to do a little bit of work.

 

String to Object Maps

Why can’t we just implement Dictionary as an ordinary Object like this?

// ActionScript:
public dynamic class Dictionary extends Object
{
}

Everything would work if we only used strings for keys:

// ActionScript:
var d : Dictionary = new Dictionary();
d["a"] = 1;
d["b"] = 2;
trace( "a=" + d["a"] ); // "a=1"
trace( "b=" + d["b"] ); // "b=2"
// JavaScript:
var d = new Dictionary();
d["a"] = 1;
d["b"] = 2;
trace( "a=" + d["a"] ); // "a=1"
trace( "b=" + d["b"] ); // "b=2"

But things wouldn’t go so well if you used objects instead of strings for keys as we will see next.

 

Object to Object Maps

Consider this example:

// JavaScript:
var d = new Dictionary();
var a = {};
var b = {};
d[a] = 1;
d[b] = 2;
trace( "a=" + d[a] ); // WRONG: "a=2"
trace( "b=" + d[b] ); // "b=2"
Why are we seeing “a=2” instead of “a=1”? It’s a bit sneaky, but a and b are forcefully converted to strings when used as keys for object maps. Since a.toString() and b.toString() yield the same string “[object Object]” the second expression “d[b] = 2” overwrites the effects of the first expression “d[a] = 1”. Both keys a and b are really the same key once converted to strings. This is what’s really happening under the hood:
// JavaScript:
var d = new Dictionary();
d["[object Object]"] = 1; // a.toString()
d["[object Object]"] = 2; // b.toString()
trace( "a=" + d["[object Object]"] ); // "a=2"
trace( "b=" + d["[object Object]"] ); // "b=2"

This looks like a tough problem: How can we emulate object to object maps in JavaScript, which only supports string to object maps? Is this another nightmare?

It is not. The solution might surprise you.

 

Dictionary extends Proxy

The title says it all: Dictionary with support for object to object maps can be implemented by deriving from Proxy. As you might recall Proxy allows you to intercept access to properties. That’s exactly what we need! What if we derived Dictionary from Proxy and override getter and setter? In our setter we could add a uid to the key object, which we would then use in our getter for retrieving values.

// ActionScript:
public dynamic class Dictionary extends Proxy
{
    private var map : Object = {};
    private static var uid : uint = 0;
    override flash_proxy function setProperty(name:*, value:*):void
    {
        name.uid = ++uid;
        map[uid] = value;
    }
    override flash_proxy function getProperty(name:*):*
    {
        return map[name.uid];
    }
}

This rough first version of Dictionary actually works. FlashRT’s current implementation is a little bit more sophisticated as it optimizes string keys and also supports for-in and for-each loop iterations. But the core idea of deriving Dictionary as a Proxy turned out to be a successful strategy.

 

Semi Weak References

We already know that Weak References are bad news. But here is another weird discovery: Our Proxy based implementation of Dictionary kind of supports weak references, because our Dictionary does not keep any references to the keys. The values are still referenced, though. Hence “semi” weak references.
If this is confusing you, look at it from this angle. We actually have to put in some extra work if we don’t want any weak references:
// ActionScript:
public dynamic class Dictionary extends Proxy
{
    private var map : Object = {};
    private var keys : Object = null;
    private static var uid : uint = 0;
    public function Dictionary( useWeakKeys : Boolean )
    {
        if( !useWeakKeys ) { keys = {}; }
    }
    override flash_proxy function setProperty(name:*, value:*):void
    {
        name.uid = ++uid;
        map[uid] = value;
        if( keys ) { keys[uid] = name; }
    }
    override flash_proxy function getProperty(name:*):*
    {
        return map[name.uid];
    }
}
Unfortunately “semi” weak references are not weak references as supported by ActionScript. That means we still have to pick one of the workarounds I came up with in my post about Weak References. The irony is that we ended up adding support for strong references to our Dictionary class.

8 Responses to Dictionary

  1. Hello
    That implementation of semi-week reference can emulate some behavior of the ActionScript Dictionary.
    But what i would like to know is how you will emulate for-in loop on a weak dictionary.

    Some ActionScript library use weak key Dictionary like discribed on this post :
    http://www.richardlord.net/blog/create-your-own-weak-references-in-actionscript-3

    I don’t see how there would be a way to do that in JavaScript.

    • Bernd Paradies says:

      Hello,

      Implementing for-in and for-each in Proxy is quite complicated. But I’ll show it if more people are interested in it.

      The article you referred to explains how you can use a Dictionary in a more generalized way for some sort of Weak Reference class. If you look at the implementation of get() you can see that the code returns the value part of a Dictionary. The for-in loop construction is not really the important detail. FlashPlayer supports weak references for Dictionary keys *and* values. The method that I described only supports weak references for Dictionary keys. Values still remain strongly referenced in my proposed solution.

      In short, I agree with you: Richard’s implementation of WeakRef would not really work in JavaScript.

      • Sorry to continue the talk, but i’m really confused by your answer.
        I always thought that only keys of Dictionary supported weak references, And when i read the asdoc of the weakKeys parameter, it says :
        “weakKeys:Boolean (default = false) — Instructs the Dictionary object to use “weak” references on object keys.”

        And when Richard do :
        for( var item:* in dic ) {
        return item;
        }

        Item is the key, is it not ?

        • Bernd Paradies says:

          Oops, you are right. Richard does store the key as a weak reference and that for-in loop does return the key. I claimed that my proposed implementation of Dictionary supports weakly referenced keys. But it’s only “kind of” and I should have made that more clear. My Dictionary only stores the UID as the keys and not the keys – that’s why keys are not referenced. That is just enough information for retrieving the value from a *given* key object. The for-in loop above would in my Dictionary implementation return the UID of the key object, not the key object (if weakKeys is true).
          That’s completely useless!
          No matter how how I look at this problem, weak references are bad news and cannot be emulated in JavaScript…
          Does that answer your question?

  2. Yes it’s more clear now, thanks a lot.

    Perhaps it would be best to throw an error at runtime when someone try to for-in on weak dictionary, since all the library which are base on this concept will result in unexpected behavior (and for example i think that the Pimento cache use similar concept).

    Anyway like i said on my first comment, if this is the only one feature which is lost when cross-compiling in javascript, that’s a pretty good news.

    Thanks a lot for this article series, which are really interesting.

  3. Bernd Paradies says:

    Thanks! I agree that it would be best to throw an error if someone tries to use for-in loops with a weak Dictionary. Actually, I think the whole weak key emulation is so messy, I would probably throw if useWeakKeys is set to true in the ctor.

    Thanks so much for pointing out this problem. I will add a little update chapter referring to our discussion.

  4. I just like the helpful information you supply for your articles. I’ll bookmark your blog and test once more here frequently. I’m somewhat certain I will