--- /dev/null
+/*
+ Copyright 2010 James Halliday (mail@substack.net)
+
+ This project is free software released under the MIT/X11 license:
+ http://www.opensource.org/licenses/mit-license.php
+
+ Copyright 2010 James Halliday (mail@substack.net)
+
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ THE SOFTWARE.
+ */
+
+var traverse;
+
+(function(){
+ traverse = function (obj) {
+ return new Traverse(obj);
+ };
+
+ function Traverse (obj) {
+ this.value = obj;
+ }
+
+ Traverse.prototype.get = function (ps) {
+ var node = this.value;
+ for (var i = 0; i < ps.length; i ++) {
+ var key = ps[i];
+ if (!node || !hasOwnProperty.call(node, key)) {
+ node = undefined;
+ break;
+ }
+ node = node[key];
+ }
+ return node;
+ };
+
+ Traverse.prototype.has = function (ps) {
+ var node = this.value;
+ for (var i = 0; i < ps.length; i ++) {
+ var key = ps[i];
+ if (!node || !hasOwnProperty.call(node, key)) {
+ return false;
+ }
+ node = node[key];
+ }
+ return true;
+ };
+
+ Traverse.prototype.set = function (ps, value) {
+ var node = this.value;
+ for (var i = 0; i < ps.length - 1; i ++) {
+ var key = ps[i];
+ if (!hasOwnProperty.call(node, key)) node[key] = {};
+ node = node[key];
+ }
+ node[ps[i]] = value;
+ return value;
+ };
+
+ Traverse.prototype.map = function (cb) {
+ return walk(this.value, cb, true);
+ };
+
+ Traverse.prototype.forEach = function (cb) {
+ this.value = walk(this.value, cb, false);
+ return this.value;
+ };
+
+ Traverse.prototype.reduce = function (cb, init) {
+ var skip = arguments.length === 1;
+ var acc = skip ? this.value : init;
+ this.forEach(function (x) {
+ if (!this.isRoot || !skip) {
+ acc = cb.call(this, acc, x);
+ }
+ });
+ return acc;
+ };
+
+ Traverse.prototype.paths = function () {
+ var acc = [];
+ this.forEach(function (x) {
+ acc.push(this.path);
+ });
+ return acc;
+ };
+
+ Traverse.prototype.nodes = function () {
+ var acc = [];
+ this.forEach(function (x) {
+ acc.push(this.node);
+ });
+ return acc;
+ };
+
+ Traverse.prototype.clone = function () {
+ var parents = [], nodes = [];
+
+ return (function clone (src) {
+ for (var i = 0; i < parents.length; i++) {
+ if (parents[i] === src) {
+ return nodes[i];
+ }
+ }
+
+ if (typeof src === 'object' && src !== null) {
+ var dst = copy(src);
+
+ parents.push(src);
+ nodes.push(dst);
+
+ forEach(objectKeys(src), function (key) {
+ dst[key] = clone(src[key]);
+ });
+
+ parents.pop();
+ nodes.pop();
+ return dst;
+ }
+ else {
+ return src;
+ }
+ })(this.value);
+ };
+
+ function walk (root, cb, immutable) {
+ var path = [];
+ var parents = [];
+ var alive = true;
+
+ return (function walker (node_) {
+ var node = immutable ? copy(node_) : node_;
+ var modifiers = {};
+
+ var keepGoing = true;
+
+ var state = {
+ node : node,
+ node_ : node_,
+ path : [].concat(path),
+ parent : parents[parents.length - 1],
+ parents : parents,
+ key : path.slice(-1)[0],
+ isRoot : path.length === 0,
+ level : path.length,
+ circular : null,
+ update : function (x, stopHere) {
+ if (!state.isRoot) {
+ state.parent.node[state.key] = x;
+ }
+ state.node = x;
+ if (stopHere) keepGoing = false;
+ },
+ 'delete' : function (stopHere) {
+ delete state.parent.node[state.key];
+ if (stopHere) keepGoing = false;
+ },
+ remove : function (stopHere) {
+ if (isArray(state.parent.node)) {
+ state.parent.node.splice(state.key, 1);
+ }
+ else {
+ delete state.parent.node[state.key];
+ }
+ if (stopHere) keepGoing = false;
+ },
+ keys : null,
+ before : function (f) { modifiers.before = f },
+ after : function (f) { modifiers.after = f },
+ pre : function (f) { modifiers.pre = f },
+ post : function (f) { modifiers.post = f },
+ stop : function () { alive = false },
+ block : function () { keepGoing = false }
+ };
+
+ if (!alive) return state;
+
+ function updateState() {
+ if (typeof state.node === 'object' && state.node !== null) {
+ if (!state.keys || state.node_ !== state.node) {
+ state.keys = objectKeys(state.node)
+ }
+
+ state.isLeaf = state.keys.length == 0;
+
+ for (var i = 0; i < parents.length; i++) {
+ if (parents[i].node_ === node_) {
+ state.circular = parents[i];
+ break;
+ }
+ }
+ }
+ else {
+ state.isLeaf = true;
+ state.keys = null;
+ }
+
+ state.notLeaf = !state.isLeaf;
+ state.notRoot = !state.isRoot;
+ }
+
+ updateState();
+
+ // use return values to update if defined
+ var ret = cb.call(state, state.node);
+ if (ret !== undefined && state.update) state.update(ret);
+
+ if (modifiers.before) modifiers.before.call(state, state.node);
+
+ if (!keepGoing) return state;
+
+ if (typeof state.node == 'object'
+ && state.node !== null && !state.circular) {
+ parents.push(state);
+
+ updateState();
+
+ forEach(state.keys, function (key, i) {
+ path.push(key);
+
+ if (modifiers.pre) modifiers.pre.call(state, state.node[key], key);
+
+ var child = walker(state.node[key]);
+ if (immutable && hasOwnProperty.call(state.node, key)) {
+ state.node[key] = child.node;
+ }
+
+ child.isLast = i == state.keys.length - 1;
+ child.isFirst = i == 0;
+
+ if (modifiers.post) modifiers.post.call(state, child);
+
+ path.pop();
+ });
+ parents.pop();
+ }
+
+ if (modifiers.after) modifiers.after.call(state, state.node);
+
+ return state;
+ })(root).node;
+ }
+
+ function copy (src) {
+ if (typeof src === 'object' && src !== null) {
+ var dst;
+
+ if (isArray(src)) {
+ dst = [];
+ }
+ else if (isDate(src)) {
+ dst = new Date(src.getTime ? src.getTime() : src);
+ }
+ else if (isRegExp(src)) {
+ dst = new RegExp(src);
+ }
+ else if (isError(src)) {
+ dst = { message: src.message };
+ }
+ else if (isBoolean(src)) {
+ dst = new Boolean(src);
+ }
+ else if (isNumber(src)) {
+ dst = new Number(src);
+ }
+ else if (isString(src)) {
+ dst = new String(src);
+ }
+ else if (Object.create && Object.getPrototypeOf) {
+ dst = Object.create(Object.getPrototypeOf(src));
+ }
+ else if (src.constructor === Object) {
+ dst = {};
+ }
+ else {
+ var proto =
+ (src.constructor && src.constructor.prototype)
+ || src.__proto__
+ || {}
+ ;
+ var T = function () {};
+ T.prototype = proto;
+ dst = new T;
+ }
+
+ forEach(objectKeys(src), function (key) {
+ dst[key] = src[key];
+ });
+ return dst;
+ }
+ else return src;
+ }
+
+ var objectKeys = Object.keys || function keys (obj) {
+ var res = [];
+ for (var key in obj) res.push(key)
+ return res;
+ };
+
+ function toS (obj) { return Object.prototype.toString.call(obj) }
+ function isDate (obj) { return toS(obj) === '[object Date]' }
+ function isRegExp (obj) { return toS(obj) === '[object RegExp]' }
+ function isError (obj) { return toS(obj) === '[object Error]' }
+ function isBoolean (obj) { return toS(obj) === '[object Boolean]' }
+ function isNumber (obj) { return toS(obj) === '[object Number]' }
+ function isString (obj) { return toS(obj) === '[object String]' }
+
+ var isArray = Array.isArray || function isArray (xs) {
+ return Object.prototype.toString.call(xs) === '[object Array]';
+ };
+
+ var forEach = function (xs, fn) {
+ if (xs.forEach) return xs.forEach(fn)
+ else for (var i = 0; i < xs.length; i++) {
+ fn(xs[i], i, xs);
+ }
+ };
+
+ forEach(objectKeys(Traverse.prototype), function (key) {
+ traverse[key] = function (obj) {
+ var args = [].slice.call(arguments, 1);
+ var t = new Traverse(obj);
+ return t[key].apply(t, args);
+ };
+ });
+
+ var hasOwnProperty = Object.hasOwnProperty || function (obj, key) {
+ return key in obj;
+ };
+})();