The instanceof trap in Node.js

I am currently writing a virtual dom implementation with the aim of being able to patch virtual DOM structures into the real DOM by applying a tree diff strategy.

In order to emulate this DOM structure, I need to create a DOM representation type, something to the effect of

module.exports = VirtualDOMNode
 
function VirtualDOMNode(tagName, properties, children) {
    this.tagName = tagName
    this.properties = properties
    this.children = children
}

For this object type to be of any use, we of course need some code that operates on this structure. The plan is to create a number of functions that operate on these nodes.

So a DOM structure building function (called h) and a rendering function are implemented. It’s just a case now of writing some modules that use h and render, like widgets, for example, using the h function to generate a virtual DOM tree structure.

var h = require("h")
 
module.exports = saySomething
 
function saySomething(something) {
    // return a virtual DOM span containing the text something
    return h("span", something)
}

Here is the catch. Notice that we have required h, a module that depends on VirtualDOMNode to produce the result for us. The module h clearly must depend on a version of the VirtualDOMNode. Next suppose we go to render this structure based on code looking like

var VirtualDOMNode = require("./virtual-dom-node")</code>
 
module.exports = render
 
function render(Node) {
    if (!(Node instanceof VirtualDOMNode)) {
        return null
    }
    /// .. and the rest
}

This render function depends on a concrete version of the VirtualDOMNode, which may not be the same VirtualDOMNode as that used by the h function required by the widget. If they are indeed requiring different versions, then the VirtualDOMNode used by the h function will not be an instance of the other VirtualDOMNode used in the rendering function.

This problem is hard to detect. In all of your code and tests, you are probably using the same deduped version for everything. You never encounter this 2 module problem in your test code. It’s not until your module has matured a bit and people have built standalone widgets against the library that the problems start to appear.

This mismatch of versions would not be obvious to detect by sight because the node is a VirtualDOMNode, it’s just an instance of some other VirtualDOMNode from some other identical module loaded from somewhere else in the node_modules tree. So from reading, you’d believe the code to be valid.

Fortunately I didn’t fall foul of this, but I was notified by a friend who suffered this problem first hand… phew

Interview Question – Multiply without *


I am currently on the market for a new job (or contract work), looking to find a challenging Node.js role. I turned up to an interview at the end of December hoping for a gruelling 2 hours of technical swordsmanship. Instead I was asked the following question:

Write a function that multiplies 2 numbers together, but you’re not allowed to use the multiply operator

I smiled, mulling through the potential purposes of the exercise. My brain temporarily went into a spin-loop on floating point number multiplication emulated with byte operations. I quickly presumed the purpose of the question was to see if I would over-engineer the solution.

But I notice that you have a [Computer Science with] maths degree

Ok. So it is a mathematical problem, I thought. Deep breath. By assuming it was a complexity trap, the answer popped into my head instantly, but bewildered me with its simplicity. I just scribbled the solution down in a couple of seconds:

function multiply(a, b) {
    if (b === 0) {
        return 0
    }
    return a / (1 / b)
}

Yeah that’s right

Hmm… a rather deflating outcome. When I go to an interview, I truly expect to be grilled. I want to go away thinking I did badly because the interview was purposefully challenging. Interviews give you a short window in which to observe the capabilities of your potential employees, so it should really be utilised to gain the best understanding of the candidate’s competence as possible.

Later on I started to think about other smarter ways you could do it. One way would be to exploit the infamous logarithmic identity

\(\log{a} + \log{b} = \log{ab}\)

so

\(ab = e^{\log{a} + \log{b}}\)

Which in JavaScript would be implemented as:

function multiply(a, b) {
    if (a === 0 || b === 0) {
        return 0
    }
    return Math.exp(Math.log(a) + Math.log(b))
}

Overall there are probably some very interesting ways this could be done, it’s just a shame they were not an important part of the interview.

Understanding the determinant

I was reading about determinants and what they actually represent. I’ve been working with solutions to the Ax = b problem where A has a determinant which is zero (i.e. it has no unique inverse). Determinants were always just a thing you did and there were magic properties about them. I suddenly realise why intuitively inv(A) exists iff det(A) != 0, simply from the geometric interpretation of the determinant.

The determinant of an n x n matrix represents the “signed volume”* of an n-dimensional cube after being multiplied by A (transformed by). So A is a transformation matrix. If we map to a zero volume, and thus the determinant is zero, we have zero in one of the dimensions.

Now zero is evil because multiplying everything by it yields 0. There is no information left regarding the original dimension as any value would have sufficed to obtain a zero.

Simply speaking, can you inverse 0a = 0? What is a? a is any value you like, so there is no inverse. Likewise for one of our dimensions.

So, when det(A) = 0 we have a matrix transformation that kills one of the dimensions (it maps all values onto a (hyper)plane) no matter what is transformed by it. When we write Ax = b, we know that one of b has a zero in some dimension and therefore we cannot determine exactly where we started to get a solution, since x could have any position in the deficient dimension, and this was mapped to zero in the transformation. Therefore you could potentially find infinitely many inverses since once or more of those dimensions has no constraint.

Of course when I say that it is in a dimension, we are strictly talking about any n-dimensional basis. So suppose you have a plane in R^3. You have a transformation matrix that projects all points in 3D onto that plane. So in the direction of normal to that plane, we have a scale of zero (eigen value as it happens), and thus the projection matrix is a matrix with no unique inverse.




If you’re interested and didn’t quite get what I was talking about, see http://www.youtube.com/watch?v=n-S63_goDFg

Printing VML and other printing bugs with IE8

My aim was to make an OpenLayers map control printable. In IE8, OpenLayers uses uses a VML-based renderer to render the vector features.

The first issue I came across was that VML does not print in IE8 the VML in OpenLayers does not always print.

How do I get VML to print?


This hasn’t worked for me with OpenLayers, perhaps relating to the way the layers work with relatively positioned div elements. But if you want to get a basic VML diagram printing you have to do the following

  1. The VML namespace should be added to the document before attempting to print VML. This should be used in conjunction with the behavior CSS rule below.

        document.namespaces.add('v', 'urn:schemas-microsoft-com:vml');


  2. To make VML printable you have to add a behavior CSS rule to the VML elements. Raphael achieves this by adding a class to all VML elements and then adding the behavior rule for that class

        doc.createStyleSheet().addRule(".rvml", "behavior:url(#default#VML)");



What if it doesn’t work?

If this doesn’t resolve your issues, as it doesn’t with OpenLayers, and you cannot avoid VML by using a better tool (such as the pure DOM/CSS renderer I am working on), you have three alternatives;

  • Force the page into IE7 compatibility mode
  • Rasterise the objects to an image on the server side
  • Or produce a document such as a PDF that can be printed later.

After seeing that IE7 standards would not provide a sufficient solution (due to changing the JavaScript engine), and noting that providing a PDF does not create a seamless print solution, I opted to produce an image of the OpenLayers control which can be injected into the page at print time. The image is produced using wkhtmltoimage on the server side and is injected at print time by attaching handlers to window.onbeforeprint (to inject the image into the page), and window.onafterprint (to return the DOM to its previous state). These are proprietary events of IE8 that are actually quite useful. These events execute very quickly as they trigger between the data processing. So, onbeforeprint fires before any print processing begins, and as soon as the page is ready for printing, i.e. the print preview or the print dialog becomes available, the onafterprint event fires and the document is ready print. This is nice because the page is not rendered between the events, and so no sign of this hack appears in the solution. It’s completely transparent.

A PDF can just as easily be produced using wkhtmltopdf, but this could be difficult if you haven’t completely encapsulated your entire page state and can reproduce it in another browser. In my case I had encapsulated the state of an OpenLayers control, so producing an image of it was fairly straight forward. However do note that if you want to read the data from stdout on Windows, you may notice that the binary data is a bit messed up if this bug hasn’t been addressed yet. It turns out that \n is translated to \r\n when wkhtmltoimage outputs to stdout. It’s not too hard to undo this, but hopefully this will be fixed soon.



Other anomalies in printing

Ok so that’s was one problem fixed. Now there are reports of other random printing bugs relating to pages containing a lot of data. IE8 just crashes. IE9 in IE8 standards mode works fine, but *real* IE8 crashes when trying to print pages containing large amounts of data. This may be resolved by removing any hidden DOM elements that are on the page. (We have 5 tabs containing memory-hungry images). I thought I would implement a generic solution that traverses the DOM and removes any hidden elements, and a function for returning them back to their original location. Equipped with the before/after print events, we should be able to seamlessly remove elements from the DOM and add them back again when the user wishes to print the page.

(function () {
 
    var invisible;
 
    function removeInvisible() {
        var e = document.body.firstChild,
            next,
            p,
            remove;
 
        invisible = [];
 
        while (e) {
            if (e.style && (e.style.display === 'none' || e.style.visibility === 'hidden')) {
                invisible.push({ parent: e.parentNode, child: e, next: e.nextSibling });
                next = e.nextSibling || null;
                remove = true;
            } else {
                next = e.firstChild || e.nextSibling || null;
                remove = false;
            }
 
            if (!next) {
                p = e;
                do {
                    p = p.parentNode;
                    next = p.nextSibling;
                } while (!next && p.parentNode !== document.documentElement);
            }
 
            if (remove) {
                e.parentNode.removeChild(e);
            }
 
            e = next;
        }
    }
 
    function appendInvisible() {
        var a, i;
        for (i = invisible.length - 1; i >= 0; i -= 1) {
            a = invisible[i];
            a.parent.insertBefore(a.child, a.next);
        }
        invisible = [];
    }
 
    window.onbeforeprint = removeInvisible;
    window.onafterprint = appendInvisible;
 
}());

Unfortunately, removing the hidden elements did not solve the printing bugs in our case, but it may be useful in general. (Forcing IE7 mode was actually the successful choice in this case).

On further investigation I also found other print bugs with IE8, such as DXImageTransform used with the filter property does not work. I’ve not yet seen a solution to this problem either, and I am inclined to believe it cannot be solved. The simpleCanvas library I have been working on was relying on the ability to print rotated div elements and images without the use of VML, but will have to fall back to server-side rasterisation if I want to provide this functionality in IE8.




Conclusions
Trying to get IE8 to print anything has been very difficult. My personal preference is to not support IE8 at all where complex visuals are concerned, but given that IE8 is the latest version of IE to run on Windows XP, there’s still a significant argument for supporting the browser.

I guess the best I can say is that IE8 is not designed for modern web applications, and this rather lengthy account of the problems I have experienced just trying to get the browser to print are a testament to this point. By modern standards the browser is incredibly slow, filled with odd proprietary features and very unique bugs that will of course never be resolved.

Libraries like jQuery convince us that trying to write web applications for IE8 is achievable with no additional time cost, but this is merely an illusion. Trying to support non-trivial sites in IE8 will cost you a fair amount of development time, and the results may not even justify the cost considering the significant performance issues with IE8. In the mean time you will have a lot of code specifically for supporting old browsers slowing down your site across all browsers, and you will be reluctant to use any modern features in case there is no easy option for backward compatibility.

Refusing to provide your IE8 users with anything at all isn’t really acceptable, but it requires a tiered approach. In general I favour the 2 versions approach; a limited fallback site for IE8 and any other older browser, which encourages users to upgrade to a sensible modern browser, and a full blown version that only works on the latest browsers. You should save the best experience for the users with the sense to upgrade their browsers, (or the IT departments with the sense to upgrade), and don’t waste your time trying to support advanced features in such a tricky browser.

Web Excitement

I was recently linked to Mozilla’s BrowserQuest game as a demonstration of the features of HTML5.

While I have to admit that this is a pretty neat achievement, I am sort of disappointed that we find technology like this amazing. We have been able to write similar things in Java or Flash for years, so why is this creating such a buzz? I guess the hype is over the fact that the browser vendors have been able to agree on a set of standards. We ignore the fact we can write similar applications with Java, which has been around for years. Or some people will say that this is awesome because we don’t need to install Flash or Java.

Ok you might not like Java, but that’s not the point at all. The point is that we are not discovering anything new. The technology has been around for years. Java and Flash made it possible sooner because there was little need for large egotistical corporations to unite and agree on a set of standards which they implement. It was just implemented and we could get stuff done. Had Java been stripped down and integrated with the browser, we might be have progressed much more quickly. I’m not exactly complaining though, JavaScript is so much nicer than Java in my opinion.

Every time a browser vendor thinks they are doing the web (and more likely themselves) a favour by implementing some proprietary feature, they are fragmenting the web and effectively crippling progress. This is why it’s taken so long by comparison to get where we are today. Some people might argue that the most troublesome feature emerging to date is the experimental Native Client, headed by our dearly beloved Google. I don’t argue against this as a feature, I just wish it was agreed on before hand. We know that none of Google’s competitors want to admit their competitor did something worthwhile, so without the existence of a standard from a central body, some people are going to be upset by the move. So you end up with some developers hard-coupling to a browser. While hard-coupling is only going to occur in situations where it makes sense, it is quite a sneaky tactic that will result in increased market share for that browser. It’s quite clear that adding proprietary features in beneficial to those pushing them if they are cool, but it is damaging progress to fragment in this way.

I think it’s about time the community took control over the situation. We should enforce standards where possible, disable proprietary features where possible, and kill the near-impossible to patch browsers (<= IE7). If a layer existed that would force all browsers into standards compliance by default, and it was adopted on mass, we would effectively have control over the situation. Such projects to look out for are DOM shims and ES5 polyfills.

Working together is the only way to progress.

Exciting ideas

I just had to share this. I caught up with my artistic partner in crime this evening and he has shown me what he’s managed to produce with the 3D engine prototype I mocked up.

I really love the simplicity of the style, and it looks great in motion, with the truck bobbing up and down as it drives along. Just seeing this fills me with a lot of energy to continue with the project. What I am trying to achieve is a system that makes 3D game creation simple enough for young programmers and the design oriented amongst us to build something that works well and looks good. While it’s not the latest and greatest in graphics processing, most 12 year olds are not going to grasp the complex 3D programming concepts, but they will be able to draw pictures and place objects on a canvas. Simplicity of graphics places more emphasis on game play elements and will make games suitable for porting to a large range of mobile devices. I am really looking forward to the end result of this project.

Investigating ugly solutions

I came across this question on stack overflow. The question simply asks how to persist JavaScript object state between browser refreshes. Now following the suggestion of using popups I decided to investigate if they could actually be used to achieve this. And it turns out that they can, though I would highly discourage anyone from using it. It’s unfortunate that my curiosity got the better of me, because there’s now a possibility that someone might actually use this solution…

Interestingly though, this does provide the only method for persisting object state, including persisting closure state of a function. This example works in Chrome and Firefox at least. We are able to offload function references in the popup, and re-reference them when the page refreshes. (You need to enable popups for it to work). There is, as far as I am aware, simply no other way to do this.

Todo… vs OpenGL ES 2.0

I have so many things on my todo list that it’s starting to get beyond my capabilities as a mere mortal. If you have taken a look around this site then you might notice it is a bit empty with a bunch of todos in place. One thing that is annoying me right now is the ugly URLs, which I know I can fix, I just have more pressing issues to deal with at the moment. I went against my preferred angle of attack (do it myself from scratch) and picked WordPress off the shelf to build this thing. As much as I would love to code my own blog, it sort of sits on my trivial work pile, so is unlikely to ever be done given the hoard of really interesting and difficult problems that are on my list.

The largest project on my list at the moment is a simple 3D game engine aimed to be accessible to the “technically challenged” and younger generations. Basically people with creative minds who can conceptualise things very well but find programming difficult, or young hackers-in-training. I don’t have the greatest track record for completing projects that don’t need to be completed. This is often because I don’t see the challenge as completing the project, but understanding the concepts behind what it is I want to do. This is one project I know will be sorely missed if it ends up on the abandon pile.

I am working with a brilliant guy on this. He is sort of my test subject. I do all the hackery behind the scenes and send off these things to be tested for usability and sanity. It’s quite important to remember that as a programmer your head probably works very differently to the average user, so to try and reverse roles for a second, or finding someone who has a different brain-type to yours is a very good idea indeed. I could definitely rant about the number of times I have found a system with a beautiful architecture, but the front end user has to trawl through a world of pain, but I actually have things to do today.

To cut a long story short about this, I basically aggressively used the OpenGL 1.1 spec. I know what you might be thinking… eww eww eww deprecated! But there was really little choice at the time of development. This really had to run on one of those poor Intel integrated chipsets, because these are most often found in schools. In real terms the number of machines that require this support is pretty small, but in the context of what we want to use this for, it actually makes up a massive percentage of target machines (.. a precise reckoning, I know).

So things were going pretty well, despite the lack of shader support, we had a nice simple prototype working. Then the ANGLE project came along, which has changed the game completely. This project is a big deal for me. OpenGL ES 2.0 support increases the possibilities drastically, not least because I wanted to get something running on Android, but because it provides a fallback for all those Intel chips that support DirectX 9 pretty well. That does unfortunately mean throwing away that code base I’ve been toying with since 2009, but it will be worth the change. I would have to write an OpenGL ES implementation for mobile devices anyway, so it seems like the best solution, despite prolonging the first release.