Implementing a yield iterator of object properties in JavaScript

Question

I need a true iterator that will work like this:

var haystackObj = {
        'needle': 'abc',
        'prop2': {
                'prop1': 'def',
                'prop2': {
                        'needle': 'ghi',
                },
                'needle': 'jkl',
        },
};
var needleKey = 'needle';
var iterator = {
    next: function () {
            /* 
             * WHAT CODE GOES HERE? 
             * 
             * Should return the next property, recursively, with the name 
             * equal to needleKey, of haystackObj.
             *
             */
    }
};

var value = iterator.next();
console.log(value); // -> 'abc'
value = iterator.next();
console.log(value); // -> 'ghi'
value = iterator.next();
console.log(value); // -> 'jkl'

I think this would be trivial with a for(k in o) and first-class continuations, but JS doesn't have those.

EDIT: I can only scan haystackObj once.

EDIT2: I am not looking for "a way to iterate through object properties." I am looking for an iterator of object properties. That is a huge difference. The problem is not as trivial as it may look at first glance.

Answer 1

I'm going to answer this one for posterity.

In ECMAScript 6 we have a yield statement. But lets say you're nuts and you'd like to use this feature right now. Compiled using the traceur-compiler to your plain old JavaScript, we get the following.

Input:

var iterator = function* (object) {

        for(var key in object) {
                yield key;
                for( k of iterator(object[key]) ) {
                        yield k;
                }
        }
};

var o = {
        a: 10,
        b: 11,
        c: {
                ca: 12,
                cb: 13,
        },
        d: 14,
};

var res = [];
for( key of iterator(o) ) {
        res.push(key);
}

res;

Output

var $__generatorWrap = function(generator) {
        return $traceurRuntime.addIterator({
                next: function(x) {
                        switch (generator.GState) {
                                case 1:
                                        throw new Error('"next" on executing generator');
                                case 3:
                                        throw new Error('"next" on closed generator');
                                case 0:
                                        if (x !== undefined) {
                                        throw new TypeError('Sent value to newborn generator');
                                }
                                case 2:
                                        generator.GState = 1;
                                if (generator.moveNext(x, 0)) {
                                        generator.GState = 2;
                                        return {
                                                value: generator.current,
                                                done: false
                                        };
                                }
                                generator.GState = 3;
                                return {
                                        value: generator.yieldReturn,
                                        done: true
                                };
                        }
                },
                'throw': function(x) {
                        switch (generator.GState) {
                                case 1:
                                        throw new Error('"throw" on executing generator');
                                case 3:
                                        throw new Error('"throw" on closed generator');
                                case 0:
                                        generator.GState = 3;
                                throw x;
                                case 2:
                                        generator.GState = 1;
                                if (generator.moveNext(x, 1)) {
                                        generator.GState = 2;
                                        return {
                                                value: generator.current,
                                                done: false
                                        };
                                }
                                generator.GState = 3;
                                return {
                                        value: generator.yieldReturn,
                                        done: true
                                };
                        }
                }
        });
};
var iterator = function(object) {
        var $that = this;
        var $arguments = arguments;
        var $state = 20;
        var $storedException;
        var $finallyFallThrough;
        var $__0;
        var $__1;
        var $__2;
        var $__3;
        var $__4;
        var $__5;
        var key;
        var $G = {
                GState: 0,
                current: undefined,
                yieldReturn: undefined,
                innerFunction: function($yieldSent, $yieldAction) {
                        while (true) switch ($state) {
                                case 20:
                                        $__2 = [];
                                $state = 21;
                                break;
                                case 21:
                                        $__3 = object;
                                $state = 23;
                                break;
                                case 23:
                                        for (var $__4 in $__3) $__2.push($__4);
                                $state = 25;
                                break;
                                case 25:
                                        $__5 = 0;
                                $state = 17;
                                break;
                                case 17:
                                        if ($__5 < $__2.length) {
                                        $state = 12;
                                        break;
                                } else {
                                        $state = 19;
                                        break;
                                }
                                case 11:
                                        $__5++;
                                $state = 17;
                                break;
                                case 12:
                                        key = $__2[$__5];
                                $state = 13;
                                break;
                                case 13:
                                        if (!(key in $__3)) {
                                        $state = 11;
                                        break;
                                } else {
                                        $state = 15;
                                        break;
                                }
                                case 15:
                                        this.current = key;
                                $state = 1;
                                return true;
                                case 1:
                                        if ($yieldAction == 1) {
                                        $yieldAction = 0;
                                        throw $yieldSent;
                                }
                                $state = 3;
                                break;
                                case 3:
                                        $__0 = $traceurRuntime.getIterator(iterator(object[key]));
                                $state = 7;
                                break;
                                case 7:
                                        if (!($__1 = $__0.next()).done) {
                                        $state = 8;
                                        break;
                                } else {
                                        $state = 11;
                                        break;
                                }
                                case 8:
                                        k = $__1.value;
                                $state = 9;
                                break;
                                case 9:
                                        this.current = k;
                                $state = 5;
                                return true;
                                case 5:
                                        if ($yieldAction == 1) {
                                        $yieldAction = 0;
                                        throw $yieldSent;
                                }
                                $state = 7;
                                break;
                                case 19:
                                        $state = -2;
                                case -2:
                                        return false;
                                case -3:
                                        throw $storedException;
                                default:
                                        throw "traceur compiler bug: invalid state in state machine: " + $state;
                        }
                },
                moveNext: function($yieldSent, $yieldAction) {
                        while (true) try {
                                return this.innerFunction($yieldSent, $yieldAction);
                        } catch ($caughtException) {
                                $storedException = $caughtException;
                                switch ($state) {
                                        default:
                                                this.GState = 3;
                                        $state = -2;
                                        throw $storedException;
                                }
                        }
                }
        };
        return $__generatorWrap($G);
};
var o = {
        a: 10,
        b: 11,
        c: {
                ca: 12,
                cb: 13
        },
        d: 14
};
var res = [];
for (var $__1 = $traceurRuntime.getIterator(iterator(o)), $__0; !($__0 = $__1.next()).done;) {
        key = $__0.value;
        {
                res.push(key);
        }
}
res;

So yield statement in JavaScript, possible, but highly impractical.

What I actually ended up using

Usage example:

var object = {...};
var callback = function (key, value) {

        // Do stuff...

        return traverse.CONTINUE; 
        // or return traverse.STOP if you want the iteration to stop
};

traverse(object, callback);

Implementation:

var traverse = (function () {

        var _traverse = function (object, callback) {

                var key, value, command;
                for( key in object ) {
                        value = object[key];

                        command = callback(key, value);
                        if( command === _traverse.STOP ) {
                                return _traverse.STOP;
                        }

                        command = _traverse(value, callback);
                        if( command === _traverse.STOP ) {
                                return _traverse.STOP;
                        }
                }
        };
        _traverse.CONTINUE = 1;
        _traverse.STOP = 2;

        return _traverse;
})();

Answer 2

Properties order is not guaranteed in JS. Different engines behave differently. (Some engines based on alphabetical order, other based on last added order.)

Your requirements are thus impossible to fulfill.

If you just wanted an iterator without minding the order, you could take a look at this question/answers: How to simulate JavaScript yield?

This is what the spec says about the properties order:

The mechanics and order of enumerating the properties (step 6.a in the first algorithm, step 7.a in the second) is not specified. Properties of the object being enumerated may be deleted during enumeration. If a property that has not yet been visited during enumeration is deleted, then it will not be visited. If new properties are added to the object being enumerated during enumeration, the newly added properties are not guaranteed to be visited in the active enumeration. A property name must not be visited more than once in any enumeration.

In reality however, you can expect a certain order from most browsers: Elements order in a "for (… in …)" loop

The only way I see to implement a fake generator (according to the fact that the order in reality suits you) would be to copy your object, and delete the scanned properties of the copy when needed. This'd mean you wouldn't rescan twice the same properties. Some code example:

var Iterator = function() {
    var copy = $.extend(haystackObj, true);
    // ^ using jQuery's extend for a quick function, but use w/e you want.
    // Anyway keep it in a closure. This copy will have its properties deleted
    // after each iteration.

    return {
        next: function next() {
            var found = false,
                needle;
            for (var prop in copy) {
                if (typeof copy[prop] === 'object') {
                    // Since next() doesn't take any argument...
                    // That's a bad solution. You should use an inner function
                    // to recurse. But I'm going to bed right now!
                    var copyCopy = $.extend(copy, true);
                    copy = copy[prop];
                    found = next();
                    copy = copyCopy;
                }

                else {
                    if (prop === needleKey) {
                        found = true;
                    }
                }

                if (found) {
                    needle = copy[prop];
                }

                // Delete the current property to simulate a real generator.
                delete copy[prop];

                if (found) {
                    return needle;
                }
            }
        }
    };
};

// Usage:
var iterator = Iterator();
iterator.next(); // "abc"

This code doesn't work (see jsfiddle), and I'm going to sleep. But you can see where it's going and how you could make something.

Answer 3

Assuming I understand you correctly, and bearing in mind that this is not a 'true yield', and putting all the code where you seem to want it,

var iterator = {
    next: function () {
        /* 
        * WHAT CODE GOES HERE? 
        * 
        * Should return the next property, recursively, with the name 
        * equal to needleKey, of haystackObj.
        *
        */
        var values=[], findneedles;
        findneedles = function(o){
            var k;
            for(k in o){
                if(k === needleKey){
                    values.push(o[k]);
                }else if(typeof o[k] === 'object'){
                    findneedles(o[k]);
                }
            }
        };
        findneedles(haystackObj);
        this.next = function(){
            return values.shift();
        };
        return values.shift();
    }
};

Answer 4

Although Florian Margaine's answer points out that the order of the properties are dependent on the js engine, this solution works in chrome. Took me a little bit of tweaking, but here it is http://jsfiddle.net/6zCkJ/3/: Edited (this solution was done before OP said the tree can only be processed once)

var needleKey = 'needle';
var currIndex = 0;
var runningIndex = 0;
var getValueByIndex = function (obj) {
    var objToSearch = obj || haystackObj;
    for (var x in objToSearch) {
        if (x == needleKey) {

            if (runningIndex == currIndex)  {
                currIndex += 1;
                return objToSearch[x];
            }
            runningIndex += 1;
        } else if (typeof objToSearch[x] == 'object') {
            var found = getValueByIndex(objToSearch[x]);
            if (found) return found;
        }

    }
}

var iterator = {
    next: function () {
        runningIndex = 0;
        return getValueByIndex(0);
    }
};

Another approach which will only traverse the tree a single time is as follows http://jsfiddle.net/6zCkJ/6/. The catch is that you must load the values array whenever the needle is updated:

var currIndex = 0;
var valuesArray = [];

var loadValues = function (obj) {
    var objToSearch = obj || haystackObj;
    for (var x in objToSearch) {
        if (x == needleKey) {
            valuesArray.push(objToSearch[x])
        } else if (typeof objToSearch[x] == 'object') {
            loadValues(objToSearch[x]);
        }
    }
}

loadValues();
console.log(valuesArray);
var iterator = {
    next: function () {
        return valuesArray[currIndex++];
    }
};

Edit: So far all answers posted here involve having to navigate the whole tree at least once or more which is not what the OP is looking for, including having to copy the object and remove properties as they are traversed. There is a solution though which involves marking the objects as they traversed with meta data which allows you to skip over the objects the next time they are encountered. Using my first approach it would be rather trivial to add these optimizations and hopefully accomplish what the OP is requesting.

Alright, so I couldn't resist trying to get this to work. Here is how I did it http://jsfiddle.net/6zCkJ/12/ . You can see that I am storing the found objects in the foundObjects object, where the key is made up of the path to that object so you can do a quick lookup to see if it has already been recursed over. The numFound is used to increment the running index properly. I have not tested this heavily, but it should be a good start:

var Iterator = function () {
    var needleKey = 'needle';
    var currIndex = 0;
    var runningIndex = 0;
    var foundObjects = {};

    var getValueByIndex = function (obj,currentPath) {
        var objToSearch = obj || haystackObj;
        for (var x in objToSearch) {
            currentPath += x + '_';
            if (x == needleKey) {

                if (runningIndex == currIndex) {
                    currIndex += 1;
                    if (!foundObjects[currentPath]) {
                        foundObjects[currentPath] = {
                            numFound: 0,
                            finished: false
                        };
                    }
                    foundObjects[currentPath].numFound += 1;
                    return objToSearch[x];
                }
                runningIndex += 1;
            } else if (typeof objToSearch[x] == 'object') {
                if (foundObjects[currentPath] && foundObjects[currentPath].finished) {
                    runningIndex += foundObjects[currentPath].numFound;
                } else {
                    var found = getValueByIndex(objToSearch[x],currentPath);
                    if (found) {
                        return found;
                    }
                }
            }
            if (!foundObjects[currentPath]) {
                foundObjects[currentPath] = {
                    numFound: 0,
                    finished: true
                };
            }
            foundObjects[currentPath].finished = true;
        }
    }

    this.next = function () {
        runningIndex = 0;

        return getValueByIndex(0,'');
    }
};
var iterator = new Iterator();
var value = iterator.next();