JavaScript bottom-up tree transformer aimed for performance function transform(tree,fn){
    var root = tree,
        node = tree,
        child,
        parent,
        is_node,
        dir;
    root.dir = 0;
    while(true) {
        is_node = typeof(node)==="object";
        dir = is_node ? node.dir : 2;
        if (dir &lt; 2)
            child = node[dir],
            node.dir++,
            child.parent = parent = node,
            child.dir = 0,
            node = child;
        else if ((changed = fn(node))!==undefined)
            changed.parent = parent,
            changed.dir = 0,
            node = changed;
        else
            if (!parent)
                return node;
            else
                parent[parent.dir-1] = node,
                node = parent,
                parent = node.parent;
    };
};

// TEST
var tree = [[1,2],[[3,4],[5,6]]];
console.log(
    JSON.stringify(transform(tree,function(a){
        if (a[0]===1) return [3,[5,5]];
        if (a[0]===5) return 77;
    })) === "[[3,77],[[3,4],77]]");


I need to make this function as fast as possible, no matter what. I'm aware this is far from the optimal implementation. How could I improve it? Asm.js, maybe?
Hmmm,

I don't think your code works,

var tree = [[1,2,[1,2,[5]]],[[3,4],[5,6]],[1,2,[1,2,[5]]],[[3,4],[5,6]]];


gives

[[3, 77], [[3, 4], 77], [1, 2, [1, 2, [5]]], [[3, 4], [5, 6]]]


I would have expected that you want that last [5,6] to be 77 in your fiddle.

Furthermore, as RoToRa mentioned


It is not clear in your code what you want to achieve
Comma separated statements to avoid curly braces are evil, python much?
Going through a tree pretty much asks for a recursive solution because you need to keep track of where you are


This function seems to do what you want thru recursion:

function transform( node, f )
{
  node = f(node) || node;  
  var index = node.length;
  if( index )
  {
    while( index-- )
    {
      node[index] = transform( node[index] , f );
    }
  }  
  return node;
}


Or, if you drop those curlies which you seem to like:

function transform( node, f )
{
  node = f(node) || node;  
  var index = node.length;
  if( index )
    while( index-- )
      node[index] = transform( node[index] , f );
  return node;
}


I originally wanted to use [].map which would be cleaner, however you insisted speed.

Update: I checked jsperf for the fastest loop and it turns out there is a new loop variant that blows the other approaches out of the water: http://jsperf.com/loops/142

Using this approach the code would look like this:

function transform( node, f )
{
  node = f(node) || node;  
  if( node.length )
    for (var i = 0, child; child = node[i]; i++)
      node[i] = transform( child , f );
  return node;
}