A Better JavaScript Generic Type Implementation

download source code

download this article in .doc format.

Overview

In a recent article I presented a simple implementation of a generic type system in JavaScript. Please see that document for a detailed enumeration of the motivations and benefits, including type safetly and Visual Studio intellisense support.

In this document I will present a 'better' implementation that eliminates many of the limitations of my 'simple' generic type implementation.

I will also provide a starter library of generic compatible collections including Queue, ListArray and Dictionary that you may use immediately and that can serve as a reference for implementing your own generic types in JavaScript.

Features:

• Full Visual Studio 2008 JavaScript Intellisense design time support.
• Multiple type parameters.
• Run time type safety.

Limitations

• No constraint implementation.
  Implementing a full type system is beyond the scope of my intentions so it will be left to the user to document proper usage of a generic type.
• Complex, nested object hierarchies or objects with novel construction strategies may not be suitable as candidates for a generic type.
• Only one generation is supported. e.g. You may not declare a generic type with a base class that has, itself, been generated as a generic type.
  This is a somewhat artificial limitation that I have imposed by removing parameter type and typecheck tokens upon creation.
  A more robust parsing engine could remove this limitation but certain browser limitations would narrow the scope of the base functionality.

Usage

Type parameter declaration for input parameters and return types is accomplished via the use of comments  in a format compatible with Visual Studio 2008 XML Comment documentation.

This has the added benefit of enhancing the design time experience in Visual Studio but in no way limits the usage of the generic type system to Visual Studio.

Listing 1 presents the full prototype of the included dictionary implementation. It has been adorned with XML comments making it consumable by the generic type system and with 'void' tags to indicate to the generic compiler where to emit typechecking expressions.

Dynamically creating an entire type checking expression is necessary as the parameter type is not known until compile type and various types require different comparison strategies.

A generic factory method has been added as a property of the function itself. The usage of the generic type system can be inferred from the comments in this method as well as the following listing.

Note that the object is fully functional as is and that no functional changes have been made to the source code so it may be used as an untyped dictionary as-is. The same is true of the other included collection classes.

Listing 1: XML comment and void tag usage

Dictionary.prototype.getAllKeys = function()
{
    /// <returns type="Array"/>
    return this._getAllKeys();
};
Dictionary.prototype.contains = function(key)
{
    /// <param name="key" type="Object" typeparam="$K$"/>
    /// <returns type="Boolean"/>
    /// <exception cref="Error">ArgumentException if key type is null or undefined</exception>
    /// <exception cref="Error">ArgumentException if key type is invalid</exception>
    void ("typecheck:key:$K$;");
    return this._contains(key);
};
Dictionary.prototype.getItem = function(key)
{
    /// <param name="key" type="Object" typeparam="$K$"/>
    /// <returns type="Object" typeparam="$V$"/>
    /// <exception cref="Error">ArgumentException if key type is null or undefined</exception>
    /// <exception cref="Error">ArgumentException if key type is invalid</exception>
    void ("typecheck:key:$K$;");
    return this._get(key);
};

Dictionary.prototype.putItem = function(key, value)
{
    /// <param name="key" type="Object" typeparam="$K$"/>
    /// <param name="value" type="Object" typeparam="$V$"/>
    /// <exception cref="Error">ArgumentException if key type is invalid</exception>
    /// <exception cref="Error">ArgumentException if key type is null or undefined</exception>
    /// <exception cref="Error">ArgumentException if value type is invalid</exception>
    void ("typecheck:key:$K$;");
    void ("typecheck:value:$V$;");
    this._put(key, value);
};
Dictionary.prototype.removeItem = function(key)
{
    /// <param name="key" type="Object" typeparam="$K$"/>
    /// <returns type="Object" typeparam="$V$"/>
    /// <exception cref="Error">ArgumentException if key type is null or undefined</exception>
    /// <exception cref="Error">ArgumentException if key type is invalid</exception>
    void ("typecheck:key:$K$;");
    return this._remove(key);
};

Dictionary.createGenericType = function(keyType, valueType, typeName)
{
    /// <summary>A generic factory method</summary>
    /// <param name="keyType" type="String">The typename of an existing type to be used as the key.</param>
    /// <param name="valueType" type="String">The typename of an existing type to be used as the value.</param>
    /// <param name="typeName" type="String">The fully qualified name of the type you wish to create. Must not exists in current scope.</param>
    /// <returns type="Object">the generated type</returns>
    /// <exception cref="Error">TypeLoadException is salient.generic is not loaded</exception>
    if (typeof (salient.generic) === "undefined")
    {
        throw salient.util.createException("salient.collections.Dictionary.createGenericType", "TypeLoadException", "salient.generic is not loaded");
    }
    return salient.generic.createGenericType("salient.collections.Dictionary", { $K$: keyType, $V$: valueType }, typeName);
}; 

Listing 2: salient.generic.createGenericType()

salient.generic.createGenericType = function(sourceTypename, typeParams, genericTypename)
{
    /// <param name="sourceTypename" type="String">The typename of an existing type which has been properly annotated for generic use.</param>
    /// <param name="typeParams" type="Object">An associative array of typeParam:typeName. e.g. {$K$:"String",$V$:"MyType"}</param>
    /// <param name="genericTypename" type="String" optional="true">Optional. If not specified a dynamic typename will be generated.</param>
    /// <returns type="Object">the generated type</returns>
}

To declare a generic Dictionary of key:String, value:RegExp you would use the following expression.

Listing 3: Generic Dictionary of String,RegExp

salient.generic.createGenericType("Dictionary", { $K$: "String", $V$: "RegExp" }, "RegExpDictionary");

The type 'RegExpDictionary' is now available for instantiation and use.

Listing 4: Examples of  emitted typecheck expressions

// Boolean - typeof check
if ((typeof (element) !== 'undefined' || element !== null) && typeof (element) !== 'boolean')
{
    throw salient.util.createException('ListOfNumbers', 'ArgumentException', 'element must be boolean value'); 
};

// Number - typeof check
if ((typeof (element) !== 'undefined' || element !== null) && typeof (element) !== 'number')
{
    throw salient.util.createException('ListOfNumbers', 'ArgumentException', 'element must be a number'); 
};

// String - typeof check
if ((typeof (element) !== 'undefined' || element !== null) && typeof (element) !== 'string')
{
    throw salient.util.createException('ListOfNumbers', 'ArgumentException', 'element must be a string'); 
};

// Date - instance check
if ((typeof (element) !== 'undefined' || element !== null) && !(element instanceof Date))
{
    throw salient.util.createException('ListOfNumbers', 'ArgumentException', 'element must be of type Date'); 
};

// RegExp - instance check
if ((typeof (element) !== 'undefined' || element !== null) && !(element instanceof RegExp))
{
    throw salient.util.createException('ListOfNumbers', 'ArgumentException', 'element must be of type RegExp'); 
};

// Error - instance check
if ((typeof (element) !== 'undefined' || element !== null) && !(element instanceof Error))
{
    throw salient.util.createException('ListOfNumbers', 'ArgumentException', 'element must be of type Error'); 
};

// arbitrary object - instance check
if ((typeof (element) !== 'undefined' || element !== null) && !(element instanceof salient.collections.ArrayList))
{
    throw salient.util.createException('ListOfNumbers', 'ArgumentException', ' element must be of type salient.collections.ArrayList'); 
};

Typecheck expressly ignores null and undefined values and only throws an exception if the object being checked is not null or undefined and is not of the indicated type.  It is left to the implementor of the generic type to guard null as is appropriate for the method.

The current type checks are, as you can see, rather strict. It is on my TODO list to add a flag to the void tag to indicate some degree of implicit type conversion. e.g. Number to String and numeric string literals to Number.

Simple List Example Revisited

In the interest of continuity I will refit the prima facia example from the previous article, List, as a generic type.

Listing 5: Simple List with generic type paramter

var List = function()
{
    /// <summary>
    /// A simple List class that is generic compatible with an
    /// element type parameter $V$
    /// Suitable for demo purposes
    /// </summary>
    /// <returns type="List"/>

    // a simple casting helper. e.g. var x = List(y);
    if (arguments[0] && (arguments[0] instanceof List))
    {
        return arguments[0];
    }

    this.innerList = [];
}

List.prototype.AddItem = function(item)
{
    /// <summary>
    /// Adds an item to this List
    /// </summary>
    /// <param name="item" type="Object" typeparam="$V$"></param>
    /// <returns type="Number">The index of the added item</returns>

    
    void ("typecheck:item:$V$;");

    return this.innerList.push(item)
}

List.prototype.GetItem = function(index)
{
    /// <summary>
    /// Gets the item at the specified index
    /// </summary>
    /// <param name="index" type="Number">the index of the desired item</param>
    /// <returns type="Object" typeparam="$V$">the item at the specified index</returns>
    /// <remarks></remarks>

    return this.innerList[index];
}

List.prototype.SetItem = function(index, item)
{
    /// <summary>
    /// Sets or replaces the item at the specified index
    /// </summary>
    /// <param name="index" type="Number">the index of the item to replace</param>
    /// <param name="item" type="Object" typeparam="$V$">the replacement item</param>
    
    void ("typecheck:item:$V$;");

    this.innerList[index] = item;
}



// A typesafe list of numbers
salient.generic.createGenericType("List", { $V$: "Number" }, "ListOfNumbers");

Listing 6: Generated Source for ListOfNumbers

ListOfNumbers = function()
{
    /// <summary>
    /// A simple ListOfNumbers class that is generic compatible with an
    /// element type parameter Number
    /// Suitable for demo purposes
    /// </summary>
    /// <returns type="ListOfNumbers"/>

    // a simple casting helper. e.g. var x = ListOfNumbers(y);
    if (arguments[0] && (arguments[0] instanceof ListOfNumbers))
    {
        return arguments[0];
    }

    this.innerListOfNumbers = [];
}

ListOfNumbers.prototype.AddItem = function(item)
{
    /// <summary>
    /// Adds an item to this ListOfNumbers
    /// </summary>
    /// <param name="item" type="Number"></param>
    /// <returns type="Number">The index of the added item</returns>

    if ((typeof (item) !== 'undefined' && item !== null) && typeof (item) !== 'number')
    {
        throw salient.util.createException('ListOfNumbers', 'ArgumentException', 'item must be a number'); 
    };

    return this.innerListOfNumbers.push(item)
};
ListOfNumbers.prototype.GetItem = function(index)
{
    /// <summary>
    /// Gets the item at the specified index
    /// </summary>
    /// <param name="index" type="Number">the index of the desired item</param>
    /// <returns type="Number">the item at the specified index</returns>
    /// <remarks></remarks>

    return this.innerListOfNumbers[index];
};
ListOfNumbers.prototype.SetItem = function(index, item)
{
    /// <summary>
    /// Sets or replaces the item at the specified index
    /// </summary>
    /// <param name="index" type="Number">the index of the item to replace</param>
    /// <param name="item" type="Number">the replacement item</param>

    if ((typeof (item) !== 'undefined' && item !== null) && typeof (item) !== 'number')
    {
        throw salient.util.createException('ListOfNumbers', 'ArgumentException', 'item must be a number'); 
    };

    this.innerListOfNumbers[index] = item;
};

// these properties follow the MS Ajax protocol enabling the appropriate
// visual cues in intellisense as well as providing a means of type discovery
// for further extension of the type.
ListOfNumbers.__baseType = "List";
ListOfNumbers.__typeName = "ListOfNumbers";
ListOfNumbers.__typeParams = { "$V$": "Number" };
ListOfNumbers.__class = true;

And the obligatory illustrations:

Figure 1:
 
Figure 2:
 
Figure 3:
 
Figure 4:
 
Figure 5:
 
Figure 6:

Deep Type Parameters

Deep type parameter declaration simply involves the direct usage of a token in the body of a method. The usage of this technique renders the base class unsuitable for use in any context other than as a generic base type.

Listing 7: Deep Type Parameters

AList.prototype.putItem = function(name, color)
{
    /// <param name="name" type="String"/>
    /// <param name="color" type="String"/>

    var item = new $E$(name, color);
    
    this.add(item);
};

The requirements of a use case may find value in this technique. For instance, a generic dictionary implementation that uses an anonymous generic key/value pair as it's element type. For now, I leave it to the reader and will not discuss it further in this document.

Browser/Platform Support Challenges

My inital strategy was to implement all features via comments in source code. Implementation went fine and I wrote a batch of unit tests which all seemed to pass in every browser/os combination I could wrangle.

Until.

Until I wrote the negative tests. These are tests for expected exceptions. Negative tests are as important, if not more as evidenced by this case, than postitive tests.

In my negative tests I pass arguments of invalid types expecting an ArgumentException. In every browser based on the Mozilla engine all of my negative tests failed as no exception was thrown.

So I checked the generated source code and found all of the typecheck expressions missing.  The only way this could happen is if the tokens are not in the source. Guess what?

The JavaScript implementation used by all Mozilla based browsers does not provide ANY access to the actual source. The toString and toSource provide the compiled source sans comments and unused string literals. 

The generic type system will emit valid source code but without comments from which to glean typecheck tags they are basically clones of the base type. This means no runtime type checking.

This does not affect the design time benefits of intellisense in Visual Studio, which I feel are tremendous, but I could see all of my work in implementing a generic type system in JavaScript ending up as a novel idea with no practical application. But I was not giving up without a fight.

The problem of no comments in the source really only affects the typechecking tokens. Intellisense is of use only to people devving in VS and of course VS uses an IE engine for it's code editors.

I investigated a few strategies and settled on a compromise. Type checking expressions were initially emitted at the location of a comment formatted as follows:

//typecheck:key:$K$;

As noted, this token is not to be found on mozilla browsers. The final implementation, which satisfies every major and most minor browsers on Win/Mac/Linux, is as follows:

void ("typecheck:item:$V$;");

Currently typechecking is strict. I hope to implement a flag to enable some degree of implicit conversion.

Browser Compatibility Matrix

I think it is clear from the tests results below that this is a viable cross browser library.

Fully Compatible

These browsers/platforms pass the test suite fully.

•  Linux Arora 0.5
• Linux Conkeror
• Linux Firefox 3.0.13
• Linux Galeon 2.0.6
• Linux MidBrowser
• Linux Midori 0.1.2
• Linux Opera 9.64
• Linux Web Browser 2.26.1
• MacOS Firefox 3
• MacOS Firefox 3.5
• MacOS Flock 2.5.2
• MacOS OmniWeb 5.9.2
• MacOS OmniWeb622.6
• MacOS Opera 9.64
• MacOS Safari 2.0.4
• MacOS Shiira 2.2
• MacOS iCab 4.6.0
• Windows Avant Browser 11.7
• Windows Chrome 2
• Windows Crazy Browser 3.0.0 rc
• Windows Explorer 6
• Windows Explorer 7
• Windows Explorer 8
• Windows Firefox 3.013
• Windows Firefox 3.09
• Windows Firefox 3.5
• Windows MaxThon 2.5.5
• Windows Opera 9.64
• Windows Safari 3.2
• Windows Safari 4
• Windows Sleipnir 2.8.3
• Windows SlimBrowser 4.12

Partial Compatibility

There are no comments or voids in source so no runtime type checks. Valid compilable code, intellisense support but NO runtime typechecking.

• Mozilla 1.8 - 2
  • Linux Seamonkey 1.1.17
  • MacOS Camino 1.6.8
  • MacOS SeaMonkey 1.1.17
  • Windows K-Meleon 1.5.3
  • Windows Seamonkey 1.1.17
  • Windows Firefox 2

Total Failure

These C grade browsers failed to even load the scripts

• Linux Dillo
• Linux NetSurf
• Windows Amaya 11.1.2
• Windows Opera 8.54

Implementation Details

Though the implementation is not exactly trivial, the concept is a fairly simple and revolves around manipulating the source code of an object with regular expressions and then compiling it with a call to eval.

1. Ensure the constituent types exist and are instantiatable and that the new generic typename does not exist.
2. Get the source code for the base type.
   1. get the constructor source
   2. append the source for all prototype members
   3. append the source for all instance members
3. Replace, globally, the base type's name with the new generic typename.
4. Replace, globally, type parameter tokens with their new specific type names.
5. Replace, globally, void ("typecheck"); tags with type checking expressions that are suitable for the type.
6. Scan for type/typeparam pairs, copy value of typeparam to type and delete typeparam attribute.
7. evaluate the resultant source code in the current scope.

In The Box

1. A zip file containing only the source files for this article.
   1. salient.generic.exerpt.js
      Contains the various namespaces and classes to support generic type creation as well as a small set of standard collection types; Queue, ArrayList and Dictionary. These classes each have a convenience method, createGenericType(), which simplifies the declaration.
      You will also find a KeyValue pair class that is generic compatible that you may find of use.
      NOTE: the namespaces contained in this file have been truncated to only the classes necessary to support the generic type system. A full release of salientJS is forthcoming.
   2. demo.js
      Contains our friend 'List' and the generic declaration of 'ListOfNumbers'. You can experiment with type creation in this file and immediately visualize the results in the script tag of demo.htm (or another script that references demo.js).
   3. tests.htm/tests.js
      A suite of unit tests, leveraging jsunittest.js, that can serve as usage examples and guidelines for the included collection types and the createGenericType method.
   4. reflection.htm
      This is a simple tool that accepts a typename and will dump the source code. Is useful for debugging or perhaps you would like to generate hardcopy source for a strongly typed class to be used without the need for a reference to the generic typing system.
2. A Visual Studio 2008 solution containing the same source files ready for exploration of design time type creation and intellisense support.

Conclusion

The use of generic types can improve the consistency and quality of your code by introducing typesafe classes and at the same time reduce surface area and testing requirements by eliminating duplicate source code.

An added benefit for Visual Studio 2008 users is the rich intellisense support that results as a happy (and intended) side effect of leveraging the XML Comment format.

This package can also serve as a code generation tool with the use of reflection.htm.  The generated source code has only a single reference to the framework code, generation of the type checking exception, that can simply be replaced with an Error constructor.

Remember that generics are not only for collection classes. There are countless other applications for generics, even in a rudimentary implementation such as salient.generic.