A Javascript Meta-Object System, Modelled On Python's OO

mop.js

/**
 * A small meta-object protocol for describing a Python-like class system in
 * Javascript.
 *
 * In this MOP, objects are (at bottom) represented as a mapping of three things:
 *
 *  - a list of parent classes
 *  - a list representing the object's MRO
 *  - a mapping of attribute names to attributes
 * 
 * The interface to the 'machinery' of an object (that is, making the object actually
 * do things), is a function, so that objects can provide custimized behavior when
 * they are used. Thus, when you create a new object, you are really getting a function
 * back.
 * 
 * Functions for manipulating objects are described below.
 */

MOP = {}

// A pretty printer for general objects
MOP.pretty = (function(obj, indent) {
    indent = indent || '';

    if (obj === null)
        return indent + 'null';
    else if (obj === undefined)
        return indent + 'undefined';
    else if (typeof(obj) == 'string')
        return indent + '"' + obj + '"';
    else if (obj instanceof RegExp)
        return indent + obj.toString();
    else if (obj instanceof Array)
        return indent + "[" + obj.map(
            function(x) { return MOP.pretty(x, '') }
        ).join(", ") + "]";
    else if (obj instanceof Function) {
        var lines = obj.toString().split('\n');
        
        // We want consistent indentation throughout the function, so we need to remove
        // any leading indentation that may already be present.
        var head_indent = lines[0].length - lines[0].trim().length;

        return indent + lines.map( 
            function(x) { return x.slice(head_indent); }
        ).join('\n' + indent);
    }
    else if (obj instanceof Object)
    {
        var result = indent + '{\n';
        for (var property in obj)
        {
            result += MOP.pretty(property, indent + '\t') + ":\n";
            result += MOP.pretty(obj[property], indent + '\t\t') + ",\n";
        }
        result += indent + '}';
        return result;
    }
    else
        return indent + obj.toString();
});

// Clone a hash table - any other object is returned as given
MOP.clone_hash = (function(hash) {
    if (typeof(hash) != 'object' || hash == null)
        return hash;

    var clone = {};

    for (var key in hash) {
        if (hash.hasOwnProperty(key))
            clone[key] = clone(hash[key]);
    }
    return clone;
});

/**
 * META OBJECT PROTOCOL
 * --------------------
 *
 *  This metaobject protocol implements a few fundamental operations:
 *
 *   - MOP.create(meta_cls, ...) instantiates a new instance of meta_cls, passing
 *     the arguments both to the allocator (mop_new) as well as the constructor
 *     (mop_init).
 *   - MOP.hasattr(inst, attr) returns true if an instance has the given attribute,
 *     or false otherwise.
 *   - MOP.getattr(inst, attr) returns the value of the attribute in the instance
 *     if the instance possesses the attribute, or undefined otherwise.
 *   - MOP.setattr(inst, attr, value) sets the value of the attribute directly on
 *     the instance.
 *   - MOP.delattr(inst, attr) removes the attribute from the instance if it has it.
 *   - MOP.name(inst) gets the name of an instance.
 *   - MOP.attrs(inst) gets a mapping from attribute names to attribute values.
 *   - parents(inst) gets a list of parent classes for a class.
 *   - MOP.mro(inst) gets the MRO of an instance.
 *   - MOP.metacalss(inst) gets the metaclass which constructed the given instance
 *
 *  Note that most of these can be overrided by values attached to instances:
 *
 *    mop_new(metaclass, ...) should return an empty object, ready to be initialized.
 *    mop_init(inst, ...) initializes a new object (its return value is ignored).
 *    mop_hasattr(inst, attr)
 *    mop_getattr(inst, attr)
 *    mop_setattr(inst, attr, value)
 *    mop_delattr(inst, attr)
 *
 *  If you want to create a new class, you can do this:
 *
 *      var my_klass = MOP.create(MOP.MetaClass, 'MyKlass', 
 *          [parent1, parent2, ...],
 *          {
 *              'mop_init': (function(instance, x, y, z) {
 *                  // Do something with the instance
 *              })
 *          });
 *
 *  Creating an instance is simpler than creating a class, because MetaClass
 *  provides a default mop_new for all classes (which you may override). To
 *  initialize an instance of MyKlass:
 *
 *      var my_inst = MOP.create(my_klass, x, y, z);
 */

/**
 * These are the 'generic functions', which expose the basics of the MOP. They
 * are all designed to be used on instances (except MOP.create, which is meant
 * to be used on classes) - because this is a *meta-object* protocol, note that
 * all classes are instances as well. Since these dispatch to the objects
 * themselves, objects are free to override their behavior by using the 'special
 * methods' described above.
 */

// Creates a new instance of a parent class. Note that this takes any number of
// arguments besides the parent class, which are passed onto the class's
// 'mop_new' and 'mop_init' functions.
MOP.create = (function(meta_cls /*, ... */) {
    var args = Array.prototype.slice.call(arguments, [1]);

    var new_func = meta_cls('getattr', 'mop_new');
    var inst = new_func.apply(new_func, [meta_cls].concat(args));
    
    if (inst == null)
        return null;

    if (meta_cls('hasattr', 'mop_init')) {
        // Note that we don't want to call the mop_init inside of a class
        // (which is designed for instances) on the class itself, which is
        // why we search for mop_init on the metaclass rather than the class.
        var init = meta_cls('getattr', 'mop_init');
        init.apply(init, [inst].concat(args));
    }
    return inst;
});

// Figures out whether or not an attribute is in an instance
MOP.hasattr = (function(inst, attr) {
    return inst('hasattr', attr);
});

// Retrieves the value of an attribute from an instance.
MOP.getattr = (function(inst, attr) {
    return inst('getattr', attr);
});

// Assigns the value of an attribute to an instance.
MOP.setattr = (function(inst, attr, value) {
    return inst('setattr', attr, value);
});

// Removes an attribute from an instance.
MOP.delattr = (function(inst, attr) {
    return inst('delattr', attr);
});

// Gets the entire mapping of attributes for an instance.
MOP.attrs = (function(inst) {
    return inst('attrs');
});

// Gets a list of parent classes for an instance.
MOP.parents = (function(inst) {
    return inst('parents');
});

// Gets the compete resolution order of an instance.
MOP.mro = (function(inst) {
    return inst('mro');
});

// Gets the name of a class
MOP.name = (function(inst) {
    return inst('name');
});

/**
 * Linearizes an inheritance hierarchy according to the C3 method, which is
 * basically a funny topological sort which respects the order of parent
 * classes in a left-to-right fashion.
 */
MOP.c3 = (function(parents) {
    // Removes all the empty lists from a list of lists
    var filter_empty = (function(list_of_lists) {
        return list_of_lists.filter(
            function(l) { return l.length > 0; })
    });

    // Gets a list, containing the first element of the original list of lists.
    // Equivalent to (map list_of_lists car)
    var get_heads = (function(list_of_lists) {
        return list_of_lists.map(
            function(l) { return l[0]; });
    });

    // Gets a list of lists, containing all but the first element of the original
    // list of lists. Equivalent to (map list_of_lists cdr)
    var get_tails = (function(list_of_lists) {
        return list_of_lists.map(
            function(l) { return l.slice(1); });
    });

    // Converts a list of potentially nested lists into a single list containing
    // all the items in depth-first order
    var flatten = (function(tree) {
        // Note that Array.prototype.concat.apply([], [...]) is a way to concatenate all the lists
        // inside of [...]
        return Array.prototype.concat.apply([],
            tree.map(function(item) {
                if (item instanceof Array)
                    return flatten(item);
                else
                    return item
            })
        );
    });

    var mro = [];
    var parent_linears = parents.map(function(parent) { 
        return parent('mro').slice(); 
    });
    parent_linears = filter_empty(parent_linears);

    while (parent_linears.length > 0) {
        var heads = get_heads(parent_linears);
        var tails = flatten(get_tails(parent_linears));

        // Find a head which no other classes are dependant upon.
        var choices = [];

        // Why build choices in reverse? Well, we want the later classes 
        // in the inheritance order to be processed first, so that way the 
        // end up further in the back of the MRO
        while (heads.length > 0) {
            var head = heads.shift();            
            if (tails.indexOf(head) == -1 && choices.indexOf(head) == -1)
                choices.push(head);
        }

        // No suitable linearization was found - presumably there are circular
        // dependencies somewhere
        if (choices.length == 0)
        {
            console.log('Invalid MRO for %s',
                MOP.pretty(parents.map(function(x) { return x('name'); })));
            return null;
        }

        while (choices.length > 0) {
            var choice = choices.shift();
            mro.push(choice);

            // Remove the chosen class from the head of any MROs that we still have
            for (var i = 0; i < parent_linears.length; i++) {
                if (parent_linears[i][0] == choice)
                    parent_linears[i].shift();
            }
        }
        parent_linears = filter_empty(parent_linears); 
    }

    return mro;
});

/**
 * This defines the MetaClass, which defines the basic operations supported by
 * the MOP, which can then be inherited by all other classes.
 */
MOP.make_metaclass = (
function() {
    // Primitive attribute manipulation functions, which are used to bootstrap
    // how attributes are manipulated. Note that the instance data (that is, the
    // content of instance('raw')) is passed to these, and not the instances
    // themselves. However, the wrappers created by MetaClass handle the 
    // transformation.
    
    var prim_hasattr = (function(inst_data, attr) {
        var hierarchy_attrs = inst_data.mro.slice(1).map(
            (function(inst) { return inst('attrs'); }));
        hierarchy_attrs.unshift(inst_data.attribs);

        while (hierarchy_attrs.length > 0) {
            var attrs = hierarchy_attrs.shift();
            if (attr in attrs)
                return true;
        }

        return false;
    });

    var prim_getattr = (function(inst_data, attr) {
        var hierarchy_attrs = inst_data.mro.slice(1).map(
            (function(inst) { return inst('attrs'); }));

        hierarchy_attrs.unshift(inst_data.attribs);
        while (hierarchy_attrs.length > 0) {
            var attrs = hierarchy_attrs.shift();

            if (attr in attrs)
                return attrs[attr];
        }

        return undefined;
    });

    var prim_setattr = (function(inst_data, attr, value) {
        inst_data.attribs[attr] = value;
    });

    var prim_delattr = (function(inst_data, attr) {
        delete inst_data.attribs[attr];
    });

    var metaclass = (function(action /* ... */) {
        // Note that metaclass_data is defined in the scobe above this,
        // but later, since it needs to get a reference to 'metaclass'
        // itself to make metaclass_data.
        
        if (action == 'hasattr') {
            var attrib = arguments[1];
            if (attrib == null)
                return false;

            return prim_hasattr(metaclass_data, attrib);
        } else if (action == 'getattr') {
            var attrib = arguments[1];
            if (attrib == null)
                return undefined;

            return prim_getattr(metaclass_data, attrib);
        } else if (action == 'setattr') {
            var attrib = arguments[1];
            var value = arguments[2];
            if (attrib == null)
                return;

            return prim_setattr(metaclass_data, attrib, value);
        } else if (action == 'delattr') {
            var attrib = arguments[1];
            if (attrib == null)
                return;

            return prim_delattr(metaclass_data, attrib);
        } else if (action == 'attrs')
            return metaclass_data.attribs;
        else if (action == 'parents')
            return metaclass_data.parents;
        else if (action == 'mro')
            return metaclass_data.mro;
        else if (action == 'name')
            return metaclass_data.name;
        else if (action == 'metaclass')
            return metaclass_data.metaclass;
        else if (action == 'raw')
            return metaclass_data;
    });

    /**
     * Creates a class from a metaclass.
     */
    var prim_new = (function(metaclass, name, parents, attribs) {
        var class_data = {};

        var klass = (function(action /* ... */) {
            if (action == 'hasattr') {
                var attrib = arguments[1];
                if (attrib == null)
                    return false;

                var my_hasattr = prim_getattr(class_data, 'mop_hasattr'); 
                if (!my_hasattr)
                    return prim_hasattr(class_data, attrib);
                else
                    return my_hasattr(klass, attrib);
            } else if (action == 'getattr') {
                var attrib = arguments[1];
                if (attrib == null)
                    return undefined;

                var my_getattr = prim_getattr(class_data, 'mop_getattr');
                if (!my_getattr)
                    return prim_getattr(class_data, attrib);
                else
                    return my_getattr(klass, attrib);
            } else if (action == 'setattr') {
                var attrib = arguments[1];
                var value = arguments[2];
                if (attrib == null)
                    return;

                var my_setattr = prim_getattr(class_data, 'mop_setattr');
                if (!my_setattr)
                    return prim_setattr(class_data, attrib, value);
                else
                    return my_setattr(klass, attrib, value);
            } else if (action == 'delattr') {
                var attrib = arguments[1];
                if (attrib == null)
                    return;

                var my_delattr = prim_getattr(class_data, 'mop_delattr');
                if (!my_delattr)
                    return prim_delattr(class_data, attrib);
                else
                    return my_delattr(klass, attrib);
                return my_delattr(klass, attrib);
            } else if (action == 'attrs')
                return class_data.attribs;
            else if (action == 'parents')
                return class_data.parents;
            else if (action == 'mro')
                return class_data.mro;
            else if (action == 'name')
                return class_data.name;
            else if (action == 'metaclass')
                return class_data.metaclass;
            else if (action == 'raw')
                return class_data;
        });

        class_data.metaclass = metaclass;
        class_data.name = name;
        class_data.parents = parents;
        class_data.attribs = attribs;
        class_data.mro = MOP.c3(parents);
        
        // If we can't linerize the inheritance tree, than we don't know how
        // to reliably find attributes in the resulting object. Abort!
        if (class_data.mro == null)
            return null;

        // This is the default 'instance maker', which just creates an empty
        // object. Note that the new object's mop_new is suppressed so that it
        // cannot create new 'sub-instances' (without explicit work on behalf 
        // of the programmer)
        prim_setattr(class_data, 'mop_new',
            function(klass) {
                // This gets the object creation function from the metaclass
                // of the current class
                var maker = MOP.getattr(klass('metaclass'), 'mop_new');

                // Override the child's mro_new, so that it cannot make
                // instances, *unless* it overrides mro_new
                return maker(klass, name + '.instance', [], {
                    'mop_new': (function(inst) { return null; })
                });
            }
        );

        if (class_data.mro.indexOf(klass) == -1)
            class_data.mro.unshift(klass);

        // Note that the metaclass which is calling this can, in fact, be
        // something other than MetaClass. To be entirely general, we have
        // to push the metaclass's whole MRO rather than just the metaclass
        // itself.
        if (class_data.mro.indexOf(metaclass) == -1)
            class_data.mro = class_data.mro.concat(metaclass('mro'));

        return klass;
    });

    // Note that the MetaClass itself doesn't use these members, but
    // instead directly dispatches to the primitives. These are only
    // useful for derived classes/instances/etc. which use the 'mop_*' special 
    // methods to do their work.
    var metaclass_attribs = {
        'mop_new': prim_new,
        'mop_hasattr': (function(metaobject, attrib) {
            return prim_hasattr(metaobject('raw'), attrib);
        }),
        'mop_getattr': (function(metaobject, attrib) {
            return prim_getattr(metaobject('raw'), attrib);
        }),
        'mop_setattr': (function(metaobject, attrib, value) {
            return prim_setattr(metaobject('raw'), attrib, value);
        }),
        'mop_delattr': (function(metaobject, attrib) {
            return prim_delattr(metaobject('raw'), attrib);
        })
    };

    var metaclass_data = {
        'parents': [],
        'attribs': metaclass_attribs,
        'mro': [metaclass],
        'name': 'MetaClass',
        'metaclass': null,
    };

    return metaclass;
});

MOP.MetaClass = MOP.make_metaclass();