arbitrarily deep nested loops over hierarchical data

nestedLooper.js

// takes a collection, a variable length list of fns, and a function
//
// for each item in the collection the list of fns that returns a value or values
// is called, with the output from the first function being threaded into the second.
//
// it won't blow the stack.
//
// e.g
//
//   util.nestedLoops([ { items: [{ name: "bob"}, {name: "sue"}] } ], _.property("items"), _.property("name"), function(group, item, name) {
//     // { items: [...]}, { name: 'bob' }, 'bob'
//     // { items: [...]}, { name: 'sue' }, 'sue'
//	 })
function nested(xs) {
	var getLoopValues = [bottom].concat( _.initial(_.tail(arguments)) );
	var fn = _.last(arguments);
	var invokeIndex = 0;

	// if we have 3 fns, the third function application yields
	// leaf values, i.e result of getLoopValues[2] is never
	// pushed to stack, rather we loop over them and invoke
	var maxDepth = getLoopValues.length - 2;

	var valuesByDepth = [];

	var stack = [{
		depth: 0,
		index: 0,
		values: xs,
	}];

	var fixmeI = 0;

	// depth first traversal of the iteration tree
	var current;
	while(current = stack.pop()) {
		updateBacktracking();
		
		if(hasNext()) {
			var values = getValues(getNext());
		} else {
			// backtrack
			continue;
		}

		if(generatedLeaves()) {
			invoke(values);
		} else {
			push(values)
		}
	}

	function push(values) {
		stack.push({
			depth: current.depth + 1,
			index: 0,
			values: values,
		})
	}

	function updateBacktracking() {
		if(current.viaBacktrack) {
			current.index += 1;
			current.viaBacktrack = false;
		}
	}

	function getValues(item) {
		var nextValues = getLoopValues[current.depth + 1];
		return values = item === MISSING ? [MISSING] : ensureArray(nextValues(item));
	}

	function generatedLeaves() {
		return current.depth === maxDepth;	
	}

	function hasNext() {
		return current.index < current.values.length;
	}

	function getNext() {
		var item = current.values[current.index];
		stack.push(current);
		current.viaBacktrack = true;
		return item;
	}

	function invoke(values) {
		// at the bottom depth, rather than pushing values to
		// stack we invoke function once per value
		if(current.depth !== maxDepth) {
			throw new Error("invoking without full stack");
		}

		var args = new Array(getLoopValues.length);

		for(var si = 0; si < stack.length; si++) {
			var stackItem = stack[si];
			var stackValue = stackItem.values[stackItem.index]
			stackValue = stackValue === MISSING ? null : stackValue;
			args[si] = stackValue;
		}

		for(var vi = 0; vi < values.length; vi++) {
			var value = values[vi];
			value = value === MISSING ? null : value;
			args[maxDepth + 1] = value;
			args[getLoopValues.length] = invokeIndex++;
			fn.apply(null, args);
		}
	}

	function bottom() {
		throw new Error("shouldn't call bottom of tree");
	}

	function ensureArray(x) {
		return _.isArray(x) ? (x.length === 0 ? [MISSING] : x) :
													(x == null ? [MISSING] : [x]);
	}

	function MISSING() {}
}