Iteration VS Enumeration

When trying to understand a language, it is necessary to first understand the words.

iteration

the for statement (§12.6.3)

enumeration

the for in statement (§12.6.4)

While writing Enumeration and Object Oriented JavaScript, I read and reasearched (I also grew a beard and lost about 20lbs in the process). I read blogs and libraries to see what other programmers were doing. I came across a peculiar quote by Alex Russel (dojo fame).

The contortions that Ajax toolkit vendors go through to keep iteration over JavaScript objects and primitives coherent is, quite simply, insane. Much of Dojo, in particular, is designed around this problem.

—Alex Russel

Iterate Over a Primitive?

That sounds completely insane! I read through dojo.js (uncompressed), which was pretty heavily commented, but could find no such contortion.

I thought about this some more, and I'm pretty sure it's not possible.

Attempting to enumerate over a primitive value results in an Object being created. That object (including its prototype chain) is then enumerated over.

Boolean.prototype.crap = "useless";
for(var prop in true) { alert(true[prop]); }
if(!delete Boolean.prototype.crap) 
    alert("uh oh :(");

Attempting to enumerate over a primitive will result in the evaluation of the primitive in creation of an object (§9.9), just as is with the property access operators, e.g. true[ prop ] or true.valueOf() === true or 1.1255.toPrecision(4);

The internal ToObject method, in the above case, will return a Boolean object holding the value true. The property named crap is resolved in Boolean.prototype, holding the string value "useless".

How About a String?

A string value might seem to be iterated over (with some practical usefulness). In that case, a String object would be created, holding the original string value; you wouldn't actually be iterating over a string value; it would just seem like it.

The difference between a String object and a string value, is explained in my entry How Property Access Works.

Practical Example of Iteration

Objects which support some form of sequential indexing of properties can be practically iterated over (§12.6.3).

JavaScript provides two types of built-in objects that fit that description.

String

Property values are characters. indexed by a numerical String starting at "0"

Array

Property values are anything. Indexed by a numerical String starting at "0"

Iterate over an Array

An Array is an object that is specialized by its length property, it's [[put]] method, and its literal initializer syntax. Array.prototype is sometimes modified to add features that are not supported in certain browsers (like Array Extras, supported in Webkit and Gecko, but not Opera 9.2 or IE 7).

Because Array.prototype is often modified, it is not safe to enumerate over an Array (unless you have a sparse array and know how hasOwnProperty works).

Non existent properties that need to be added by programmer-defined code do not exist, and therefore, cannot have the DontEnum attribute. For example, Array.prototype.some does not exist on Array.prototype in IE or Opera, but is non-enumerable, native code in other browsers.

To avoid enumerating over a property in the prototype chain, a cautious programmer will avoid using for in on an Array, and use hasOwnProperty when he does use for in.

Library authors might consider adding only the top-level Extras, e.g. Array.some to browsers that don't have Array.some, and leaving the prototype alone.

Iterating Over a String

When the string value is converted to a String Object, the characters in the value are accessible through the object.

String.prototype has a method to access character properties: charAt (§15.5.4.4).

Here's where it gets interesting.

Gecko and Webkit implement another way access to String index properties: The property access operators [ ]. This is not part of the official specification.

String's [[Put]] method §8.6.2.2 is specialized in Webkit. This seems to create some problems, as can be shown in an example.

Example Using [] on a String object

(function(){
    String.prototype['2'] = "prot";
    String.prototype['4'] = "prot4";
    a = new String("012");
    a[1] = "one";
    a[11] = "eleven"
    var result = [];
    for(var i = 0; i < a.length; i++)
        result.push(a.charAt(i) + ", a['"+i+"'] = "+ a[i]);

    result.push(a.charAt(4)  // Should be "".
        + " , a['"+ 4 +"'] = "+ a[4] );
    
    result.push(a.charAt(11)  // Should be "".
        + " , a['"+ 11 +"'] = "+ a[11] );

    return result.join(String.nl);
})();

String.prototype.charAt works consistently in all browsers. The property access operator results are more interesting.

In Gecko and Opera, property access ([], §11.2.1) on a String checks the object for a property by the name given. If no property is found, if the string value of the property name is integral, charAt (or its equivalent) is called, passing the property, e.g aString[1.0] is evaluated as aString['1'] (§15.5.4.4).

Webkit has the opposite result. Webkit seems to have broken [[Put]] for String.

Observations on Property Access

Mozilla and Opera

• a['0'] returns the character at index 0, "0". (goes through charAt)
• a['1'] is resolved to a property, the value "one" is returned.
• a['2'] does not find a property on the object itself and does not call [[Get]]. charAt is called.
• a['11'] is resolved to a property, the value "one" is returned.

Gecko's [[Put]] results in a property being added to the object. The property will not be returned in charAt, but will be returned with [ ] (§11.2.1).

Webkit

Webkit seems to have a special algorithm for [[Put]] on String. A property P seems to be added to a String only when ToNumber(P) is greater than the String's length.

The approach Webkit takes is a bad one. I cannot see any reason why the Webkit team did this. A specialized [[Put]] might be the result of the design under the hood and was a preventative measure to keep the string from being modified (guess).

Unlike an Array, a String's length property is ReadOnly.

So we've covered enumerating over a primitive (useless), iterating over an String and an Array. What about iterating over an object?

Iterate over an Object

Its not usually practical, but it is possible

var nlist = {
  n : 1,
  nn: 2,
  nnnn: 3,
  nnnnnnnn: 3
};

if(! "console" in window) {
    document.title = "log: ";
    window.console = { log : function(s){ document.title += s; };
}
var result = "";
for( var p = "n"; nlist.hasOwnProperty(p); p+=p ) {
    console.log(nlist[p]);
}

Iterating over a BitSet as a String could be useful.

It would be possible (possibly even useful) to iterate over (or use Array or String extras with) a BitSet object. Fortunately, it's not that hard to write a BitSet class.

Enumeration is a Problem

Nearly every JavaScript library attempts to address the language limitations and browser bugs. Enumeration needlessly complicates Object. The libraries painfully show this to be true.

ECMAScript could instead provide Enum, SortedSet<T>, Map<T>, ListIterator<T>. These collections would provide safer, more powerful alternatives to the current problem.

I've provided more analysis on the problem of enumeration in my article, Enumeration and Object Oriented JavaScript

Technorati Tags: JavaScript