Implementing a DOM in JavaScript, part two: Two difficult options, with requirements and test specs

A little over a week ago, I had an idea about implementing
a DOM in JavaScript
. Thank goodness I
wasn’t the first
. (Thanks for the links, guys!)

Still, what these libraries provide isn’t enough. It’s “necessary but not
sufficient” for what I really need: using one DOM tree as a public interface to
another, “private” DOM tree. I’m calling this a “DOM Abstraction”, for lack of
a better term. So in classic do-it-yourself fashion, I set out to plan what I
needed to implement.

I just spent several hours (spread over many days) formally defining
requirements and tests. As I was reviewing my article, I asked myself a simple
question: Well, why don’t you just clone a bunch of native DOM nodes and
extend their properties?

More in the extended entry. (Warning: it’s looooooooooooooooooooooong! But I really do need developer’s feedback. I hope I’m not too boring.)

It turns out there’s a few reasons:

  • Adding interfaces to a node’s QueryInterface list, to enable callers to
    tell what the object is an instance of. (This is easily fixable in C++ – a single-line macro.)
  • Modifying native methods and properties to behave differently. (You can’t
    exactly replace Node::firstChild, unless you’re willing to write more C++
  • Implementing other DOM “classes”, like Entity and EntityReference, and
    exposing them to the DOM. (Same problem: you can’t easily add these to the
    native DOM, unless you want to hack the DOM.)
  • If both upper-layer and lower-layer nodes are native Mozilla DOM nodes,
    it becomes very hard to prevent cross-layer node operations
    (document.importNode and document.adoptNode are
    designed to take DOM nodes that otherwise belong to other documents).

Now, all of this is doable at the C++ level. The key is finding a way to
wrap all the DOM classes (nsGenericElement, etc.) in another set of scriptable
classes which (mostly) forward all method and property calls to the original
classes. But the scriptable classes also have to provide a way to
replace implementations of specific methods and properties on this
set. Basically, I’d be introducing aspect-oriented
to the C++ code for a very specific purpose.

(Guess what – if you ever replace one function in JavaScript with another,
even to call the original function at a specific time, you’re
already doing AOP!

I’m facing a dilemma. Either I write a bunch of JavaScript code,
including “a
lot of tests”
(I agree with Jonas, Mounir. Great stuff!), or I write a
bunch of C++ code with many tests, and rely on the very heavily
tested and widely used
Mozilla DOM implementation. I am perfectly capable
of doing either (I’ve written several content/… patches before), and either
way, it’s going to take me anywhere from two months to a year to complete.
Something this big I’m not good at estimating, and now I have two big options
to look at.

I can’t avoid doing this work – I went over my “why are you
doing this”
process again, and I found I really do need a DOM abstraction –
if not now, eventually (and experience has taught me not to wait for
“eventually”). My gut feeling says to continue with the JavaScript-based
solution, if I’m doing this on my own with no outside help.

So here I am, posting my thoughts for everyone to see. Bottom line, I don’t
know which solution to implement, so I’m asking for your advice, fellow
Mozillians. If you were interested and able to help out, which solution would
you pick? Which one would you pick if you knew only I was able to work on

For reference, the requirements and tests (along with my original
introduction) are below.

I’ve spent the last several days tasting the abstracted DOM idea, and I find
that it really is necessary to my goals and a good idea. I’ve also been trying
to figure out how to make sure it’s as reliable – if not better – as the
existing native DOM. This is a pretty tall order, but critical: if I’m building
a library of capabilities and I can’t guarantee it works, I don’t want to use
it. Ergo, I have to pass a pretty high reliability bar to justify using it.

So I wrote out both a requirements list to define testable conditions, and a
set of test descriptions to indicate ways I can test for deficiencies. Because
these are very long, I’m posting them in the extended entry.

Abstraction requirements

  • An abstraction first clones a DOM tree, and defines the clone as an
    “upper layer” of the original DOM tree. The original DOM tree becomes the
    “lower layer”.
  • The purpose of the upper layer is to hide interaction with the lower
    layer from all possible callers. In C++ terminology, this means the upper
    layer becomes a public interface to the lower layer, but keeps the lower
    layer private.
  • Example workflow: An iframe may load a lower layer document into
    rendering. Then an abstraction layer is built, exposing an upper layer
    document to scripts. Later, a XML file is parsed via a DOMParser into a
    lower-layer XML document, and an upper layer document for the XML file is
    built through the same abstraction. Finally, a node from the upper layer
    XML document is imported and inserted into the upper layer iframe document.
    This forces a similar import and insert on the lower level documents.
  • There is no limit to the number of abstraction layers associated with a
    particular native DOM tree. It should be possible to construct a
    third-layer abstraction which inverts the second-layer abstraction, such
    that the first layer DOM fragment and the third layer DOM fragment are
  • Except for the native DOM layer, each upper layer must have exactly one
    lower layer, and no lower layer can have more than one upper layer at a
    time. (However, a “middle” layer may have a lower layer and an upper
    layer.) Similarly, every upper layer node has a corresponding lower layer
  • No lower layer node should have more than one upper layer. (Reason: A
    private member cannot be exposed to more than one public object.)
  • The native DOM layer may have any number of upper DOM layers. The native
    DOM layer may not have any lower DOM layers. (Reason: This native DOM is
    considered “layer 1”, and could be reused in any number of different ways.
    But nodes belonging to the native layer still have the 1:1 restriction, as
    stated above.)
  • The upper layer nodes need the lower layer nodes, and will thus hold
    strong references to them. This includes attributes. Every upper layer node
    must have a strong reference to its matching lower layer nodes.
  • Once the upper layer is created, all modifications to nodes in the lower
    layer must be induced only by nodes from the upper layer, and only by the
    rules defined for the abstraction. The lower layer is otherwise frozen.
    (Reason: The upper layer is relying on the consistency of the DOM tree in
    the lower layer. If an unexpected change comes from another source,
    consistency of the lower layer cannot be guaranteed.)
  • The lower layer nodes do not need the upper layer nodes, and should never
    refer to the upper layer nodes. (Reason: The upper layer may be destroyed
    at any time, and will likely take the lower layer with it in garbage
  • An upper layer node may hold references to more than one lower layer
    node. (Example: An XBL binding on the upper layer node may reference nodes
    in the lower level, defining them as “anonymous”. Or an entity reference in
    the upper layer may reference a range of DOM nodes in the lower level.)
  • The abstraction creator should pass in a callback function. When the
    upper layer is complete, the abstraction will call the callback with the
    upper layer root node as the first argument. The callback will execute all
    initial DOM mutations on the lower layer nodes. The callback must not
    modify the upper layer nodes, and if it does, the upper DOM tree is
    considered dead.
  • A lower layer may insert nodes from the lower DOM tree which are hidden
    from the upper layer.
  • A lower layer may remove nodes from the lower DOM tree which are visible
    to the upper layer.
  • When a node is considered dead, no properties nor methods may call on
    that node except to detect that dead condition and throw an exception, and
    an exception must be thrown.
  • If at any time an upper layer node detects it cannot correctly access a
    node it controls in the lower layer, it should mark the entire upper layer
    as dead, and throw an error. (Reason: If the relationship between upper
    layer and lower layer can no longer be guaranteed correct, then the upper
    layer cannot be trusted. Therefore, we must mark the entire upper layer
  • Every abstraction layer must have an ID unique to the application’s
    session. (Reason: This is how the abstraction layer identifies an unique
    upper layer document, and JavaScripts associated with that document.)
  • No abstraction layer document may import or adopt nodes from another
    abstraction layer. (Reason: That defeats the purposes of consistency.)
  • No lower layer node entering the abstraction as a root may have a parent
    node. (Reason: When the abstraction creates the upper layer nodes, it will
    use a tree walker to establish relationships between the upper layer and
    the lower layer, starting at the root. Thus, the upper layer’s root won’t
    have a parent node. For consistency, the lower layer’s root must not have a
    parent node either.)
  • Except for document nodes, no lower layer node may enter the abstraction
    as a root unless its owner document has also entered the abstraction as a
    root. (Reason: Consistency again. We could theoretically generate a “stub”
    upper layer document to handle tasks like creating DOM nodes. But it risks
    introducing a document node without the correct child nodes, for example.
    It’s just easier to ensure consistency if the lower layer ownerDocument is
    abstracted first.)
  • JavaScript-loading elements specify the abstraction upper layer they
    execute at by modifying the type attribute to indicate the abstraction
    layer by ID. For example: <html:script
    type="application/javascript?layer=DOMEntityLayer" src="foo.js"
    . Scripts will not load in the abstraction layer until after
    the root node has been fully abstracted. (Reason: This, tied in with the
    abstraction layer ID, makes it much easier to control when scripts execute,
    and more importantly, in what scope. If you are hoping for script execution
    before the layer finishes, forget it.)
  • The abstraction will not dispatch a load event to any node or window
    object in the upper layer, under the presumption that the document has
    already loaded before the scripts in that upper layer’s scope execute.
  • An unload event, similarly, is not guaranteed for the upper layer.
    (Reason: the upper layer may already be dead. Executing a script then could
    lead to unpredictable results.)
  • Scripts executing in an upper layer should always be prepared for the
    possibility that any node in the upper layer is dead. Timeouts, etc.,
    should not execute in an upper layer’s scope.
  • If scripts in the lower layer document would not execute due to the lower
    layer document being a data document, upper layer scripts should not expect
    to execute unless explicitly invoked by the upper layer.
  • Whenever a node in the upper layer maps directly to an equivalent lower
    layer node (for instance, an element directly reflecting another element),
    the upper layer node must implement all public methods and properties of
    the lower layer node. The upper layer node in this case must react exactly
    as the lower layer node would to each of these “forwarded” methods as
    properties, except where the upper layer node’s specifications explicitly
    define an alternate behavior for a “forwarded” property or method.
    (Example: If a lower layer node has an appendChild method – which per the
    DOM Level 1 Specification it must – then the upper layer node must either
    duplicate that functionality, or have a specific alternate procedure
    defined for the appendChild method. This specific alternate procedure does
    not affect, for instance, the forwarding of the insertChild method: an
    alternate insertChild method must be specified or default to the behavior
    it would normally have under the DOM specification.) Note this requirement
    does not apply to indirect mappings. (Example: An EntityReference upper
    layer node hiding a lower layer DOM range of non-EntityReference nodes does
    not need to implement any interfaces specific to those lower layer nodes or
    the range, except for what the EntityReference DOM specifications already
  • CSS style rules from the upper layer will not apply to any nodes. If the
    abstraction wants CSS style rules to appear as if they applied, it should
    modify what the defaultView of the upper layer’s document returns.
  • Upper layer nodes must not execute any code on the lower layer
    unless there is no reasonable chance for an error or exception being thrown
    from that lower layer. The methods for upper layer nodes must validate
    arguments and throw errors or exceptions for invalid arguments before
    executing any code on the lower level.
  • When an error or an exception is thrown from (or through) a lower layer
    node, it means an extreme failure has taken place in the abstraction model.
    The entire lower layer, and all nodes belonging to it (whether in the
    current tree or not) should be considered dead. (Reason: If a lower layer
    node threw an exception, that means the validation steps at the upper layer
    were not complete! Shame on you for not checking what you were passing

Abstraction tests

  1. Use Node.cloneNode(false) and a TreeWalker to assemble a complete clone
    of a DOM tree, then call Node.isEqualNode(otherNode) to confirm the two are
    equal. (I can’t use Node.cloneNode(true), because ultimately I want to walk
    the native DOM tree to create JS-based DOM nodes.)
  2. Experiment with DOM manipulations at the upper level from step 1, and
    show the upper level and lower level remain equal through all
  3. Build a JavaScript-based “1:1 identity” DOM layer, based on envjs’s DOM
    packages, to replace the upper level in step 2. Re-run tests from step 2 to
    show consistency.
  4. Self-consistency check: Build a second JavaScript-based “1:1
    identity” DOM abstraction layer on top of the first JavaScript-based DOM
    abstraction layer. Re-run tests from step 2 to show consistency.
  5. Mixing layers test: Show that all attempts to insert nodes from one layer
    into another layer will fail, in a consistent way. (This explicitly
    includes mixing native DOM nodes with JavaScript-based DOM nodes!)
  6. Modifying lower layer nodes: Show that it’s possible to implement at
    least two different DOM abstractions, each of which modifies their lower
    layers differently and maintains consistency.
  7. Use the subscript loader to define scopes for nodes from a DOM layer to
    live in, and for HTML script elements to execute in. The scopes’ document
    object should be defined to reference the document node in the
    corresponding JS layers, and the scopes’ window object should be similarly
  8. Mozilla DOM tests: Run 3 JavaScript-based DOM layers (the”1:1 identity”
    layer, and the two DOM layers from step 6) against as many DOM Mochitests
    as possible. Use the subscript loader to define scopes for the Mochitests
    and DOM layer to run in. (This means the scope’s document object should be
    defined to reference the document node in the JS layer, and the scope’s
    window object should be similarly hidden.)
  9. Prove that each JavaScript-based DOM layer can hide and/or show different
    patterns of nodes, so as to act like a composite DOM layer.
  10. The “Inception” Test:
    • Level 0: A raw XML file
    • Level 1: Native DOM nodes from the application
    • Level 2: JS “1:1 identity” abstraction layer
    • Level 3: JavaScript abstraction layer which modifies Level 2 in a
      specific way
    • Level 4: JavaScript abstraction layer which modifies Level 3 in a
      specific way

    (Repeat after me: This DOM is not real. This DOM is not real. This
    DOM is not real…)

On this last test, logicians may wonder, “Why do you need that?” After all,
this test simply duplicates features which earlier tests already cover. My
rationale is in terms of code execution, under nearly similar conditions:

  • A lot of code can be written to run on top of other code.
  • Typically, JavaScript runs atop native code, so I don’t count that.
  • You can even write code to run on top of code that runs on top of other
  • When you get up to three levels deep in the execution stack (code on top
    of code on top of more code on top of still more code)…, and all three
    levels are fairly similar (same language, same base implementations), it’s
    a pretty good bet that you can run up to infinite levels.
  • (That is, until you hit some physical limit, like eating up too much
    memory, the heat death of the universe, or a plain-old “Too much recursion”
    state that puts you in limbo. Heaven help you if you start using
    timeouts somewhere around there…)
  • Of course, it’s not entirely certain. A thrown exception anywhere in the
    call stack can kick you out, hard.
  • Are you tired of the movie references yet? Sometimes this kind of deep
    thinking can be a real nemesis to simplicity, and possibly to good
    clean code… (Bonus points if you got that one. I didn’t notice until I
    saw it on the Internet Movie Database, and I should have!)

The important thing, to me at least, is that every condition in
“Abstraction requirements” and “Abstraction tests” is explicitly testable, one
way or another. (There are a couple, particularly around events, that aren’t
really conditions.) Therefore, if I write tests for every condition, and my
abstraction library can pass every test with no “to-do” tests left, then I have
defined conditions for which others can use my abstraction library with
confidence. Of course, it’s not guaranteed to be correct – there can always be
bugs, and performance might be an issue – but finding a failure point in the
library itself would take some doing. (As opposed to, say, a failure point in
code calling on the library.)