/*
 Copyright (c) 2012, Yahoo! Inc.  All rights reserved.
 Copyrights licensed under the New BSD License. See the accompanying LICENSE file for terms.
 */

/*global esprima, escodegen, window */
(function (isNode) {
    "use strict";
    var SYNTAX,
        nodeType,
        ESP = isNode ? require('esprima') : esprima,
        ESPGEN = isNode ? require('escodegen') : escodegen,  //TODO - package as dependency
        crypto = isNode ? require('crypto') : null,
        LEADER_WRAP = '(function () { ',
        TRAILER_WRAP = '\n}());',
        COMMENT_RE = /^\s*istanbul\s+ignore\s+(if|else|next)(?=\W|$)/,
        astgen,
        preconditions,
        cond,
        isArray = Array.isArray;

    /* istanbul ignore if: untestable */
    if (!isArray) {
        isArray = function (thing) { return thing &&  Object.prototype.toString.call(thing) === '[object Array]'; };
    }

    if (!isNode) {
        preconditions = {
            'Could not find esprima': ESP,
            'Could not find escodegen': ESPGEN,
            'JSON object not in scope': JSON,
            'Array does not implement push': [].push,
            'Array does not implement unshift': [].unshift
        };
        /* istanbul ignore next: untestable */
        for (cond in preconditions) {
            if (preconditions.hasOwnProperty(cond)) {
                if (!preconditions[cond]) { throw new Error(cond); }
            }
        }
    }

    function generateTrackerVar(filename, omitSuffix) {
        var hash, suffix;
        if (crypto !== null) {
            hash = crypto.createHash('md5');
            hash.update(filename);
            suffix = hash.digest('base64');
            //trim trailing equal signs, turn identifier unsafe chars to safe ones + => _ and / => $
            suffix = suffix.replace(new RegExp('=', 'g'), '')
                .replace(new RegExp('\\+', 'g'), '_')
                .replace(new RegExp('/', 'g'), '$');
        } else {
            window.__cov_seq = window.__cov_seq || 0;
            window.__cov_seq += 1;
            suffix = window.__cov_seq;
        }
        return '__cov_' + (omitSuffix ? '' : suffix);
    }

    function pushAll(ary, thing) {
        if (!isArray(thing)) {
            thing = [ thing ];
        }
        Array.prototype.push.apply(ary, thing);
    }

    SYNTAX = {
        ArrayExpression: [ 'elements' ],
        AssignmentExpression: ['left', 'right'],
        BinaryExpression: ['left', 'right' ],
        BlockStatement: [ 'body' ],
        BreakStatement: [ 'label' ],
        CallExpression: [ 'callee', 'arguments'],
        CatchClause: ['param', 'body'],
        ConditionalExpression: [ 'test', 'consequent', 'alternate' ],
        ContinueStatement: [ 'label' ],
        DebuggerStatement: [ ],
        DoWhileStatement: [ 'body', 'test' ],
        EmptyStatement: [],
        ExpressionStatement: [ 'expression'],
        ForInStatement: [ 'left', 'right', 'body' ],
        ForStatement: ['init', 'test', 'update', 'body' ],
        FunctionDeclaration: ['id', 'params', 'body'],
        FunctionExpression: ['id', 'params', 'defaults', 'body'],
        Identifier: [],
        IfStatement: ['test', 'consequent', 'alternate'],
        LabeledStatement: ['label', 'body'],
        Literal: [],
        LogicalExpression: [ 'left', 'right' ],
        MemberExpression: ['object', 'property'],
        NewExpression: ['callee', 'arguments'],
        ObjectExpression: [ 'properties' ],
        Program: [ 'body' ],
        Property: [ 'key', 'value'],
        ReturnStatement: ['argument'],
        SequenceExpression: ['expressions'],
        SwitchCase: [ 'test', 'consequent' ],
        SwitchStatement: ['discriminant', 'cases' ],
        ThisExpression: [],
        ThrowStatement: ['argument'],
        TryStatement: [ 'block', 'handlers', 'finalizer' ],
        UnaryExpression: ['argument'],
        UpdateExpression: [ 'argument' ],
        VariableDeclaration: [ 'declarations' ],
        VariableDeclarator: [ 'id', 'init' ],
        WhileStatement: [ 'test', 'body' ],
        WithStatement: [ 'object', 'body' ]

    };

    for (nodeType in SYNTAX) {
        /* istanbul ignore else: has own property */
        if (SYNTAX.hasOwnProperty(nodeType)) {
            SYNTAX[nodeType] = { name: nodeType, children: SYNTAX[nodeType] };
        }
    }

    astgen = {
        variable: function (name) { return { type: SYNTAX.Identifier.name, name: name }; },
        stringLiteral: function (str) { return { type: SYNTAX.Literal.name, value: String(str) }; },
        numericLiteral: function (num) { return { type: SYNTAX.Literal.name, value: Number(num) }; },
        statement: function (contents) { return { type: SYNTAX.ExpressionStatement.name, expression: contents }; },
        dot: function (obj, field) { return { type: SYNTAX.MemberExpression.name, computed: false, object: obj, property: field }; },
        subscript: function (obj, sub) { return { type: SYNTAX.MemberExpression.name, computed: true, object: obj, property: sub }; },
        postIncrement: function (obj) { return { type: SYNTAX.UpdateExpression.name, operator: '++', prefix: false, argument: obj }; },
        sequence: function (one, two) { return { type: SYNTAX.SequenceExpression.name, expressions: [one, two] }; }
    };

    function Walker(walkMap, preprocessor, scope, debug) {
        this.walkMap = walkMap;
        this.preprocessor = preprocessor;
        this.scope = scope;
        this.debug = debug;
        if (this.debug) {
            this.level = 0;
            this.seq = true;
        }
    }

    function defaultWalker(node, walker) {

        var type = node.type,
            preprocessor,
            postprocessor,
            children = SYNTAX[type].children,
            // don't run generated nodes thru custom walks otherwise we will attempt to instrument the instrumentation code :)
            applyCustomWalker = !!node.loc || node.type === SYNTAX.Program.name,
            walkerFn = applyCustomWalker ? walker.walkMap[type] : null,
            i,
            j,
            walkFnIndex,
            childType,
            childNode,
            ret,
            childArray,
            childElement,
            pathElement,
            assignNode,
            isLast;

        /* istanbul ignore if: guard */
        if (node.walking) { throw new Error('Infinite regress: Custom walkers may NOT call walker.apply(node)'); }
        node.walking = true;

        ret = walker.apply(node, walker.preprocessor);

        preprocessor = ret.preprocessor;
        if (preprocessor) {
            delete ret.preprocessor;
            ret = walker.apply(node, preprocessor);
        }

        if (isArray(walkerFn)) {
            for (walkFnIndex = 0; walkFnIndex < walkerFn.length; walkFnIndex += 1) {
                isLast = walkFnIndex === walkerFn.length - 1;
                ret = walker.apply(ret, walkerFn[walkFnIndex]);
                /*istanbul ignore next: paranoid check */
                if (ret.type !== type && !isLast) {
                    throw new Error('Only the last walker is allowed to change the node type: [type was: ' + type + ' ]');
                }
            }
        } else {
            if (walkerFn) {
                ret = walker.apply(node, walkerFn);
            }
        }

        for (i = 0; i < children.length; i += 1) {
            childType = children[i];
            childNode = node[childType];
            if (childNode && !childNode.skipWalk) {
                pathElement = { node: node, property: childType };
                if (isArray(childNode)) {
                    childArray = [];
                    for (j = 0; j < childNode.length; j += 1) {
                        childElement = childNode[j];
                        pathElement.index = j;
                        if (childElement) {
                          assignNode = walker.apply(childElement, null, pathElement);
                          if (isArray(assignNode.prepend)) {
                              pushAll(childArray, assignNode.prepend);
                              delete assignNode.prepend;
                          }
                        }
                        pushAll(childArray, assignNode);
                    }
                    node[childType] = childArray;
                } else {
                    assignNode = walker.apply(childNode, null, pathElement);
                    /*istanbul ignore if: paranoid check */
                    if (isArray(assignNode.prepend)) {
                        throw new Error('Internal error: attempt to prepend statements in disallowed (non-array) context');
                        /* if this should be allowed, this is how to solve it
                        tmpNode = { type: 'BlockStatement', body: [] };
                        pushAll(tmpNode.body, assignNode.prepend);
                        pushAll(tmpNode.body, assignNode);
                        node[childType] = tmpNode;
                        delete assignNode.prepend;
                        */
                    } else {
                        node[childType] = assignNode;
                    }
                }
            }
        }

        postprocessor = ret.postprocessor;
        if (postprocessor) {
            delete ret.postprocessor;
            ret = walker.apply(ret, postprocessor);
        }

        delete node.walking;

        return ret;
    }

    Walker.prototype = {
        startWalk: function (node) {
            this.path = [];
            this.apply(node);
        },

        apply: function (node, walkFn, pathElement) {
            var ret, i, seq, prefix;

            walkFn = walkFn || defaultWalker;
            if (this.debug) {
                this.seq += 1;
                this.level += 1;
                seq = this.seq;
                prefix = '';
                for (i = 0; i < this.level; i += 1) { prefix += '    '; }
                console.log(prefix + 'Enter (' + seq + '):' + node.type);
            }
            if (pathElement) { this.path.push(pathElement); }
            ret = walkFn.call(this.scope, node, this);
            if (pathElement) { this.path.pop(); }
            if (this.debug) {
                this.level -= 1;
                console.log(prefix + 'Return (' + seq + '):' + node.type);
            }
            return ret || node;
        },

        startLineForNode: function (node) {
            return node && node.loc && node.loc.start ? node.loc.start.line : /* istanbul ignore next: guard */ null;
        },

        ancestor: function (n) {
            return this.path.length > n - 1 ? this.path[this.path.length - n] : /* istanbul ignore next: guard */ null;
        },

        parent: function () {
            return this.ancestor(1);
        },

        isLabeled: function () {
            var el = this.parent();
            return el && el.node.type === SYNTAX.LabeledStatement.name;
        }
    };

    /**
     * mechanism to instrument code for coverage. It uses the `esprima` and
     * `escodegen` libraries for JS parsing and code generation respectively.
     *
     * Works on `node` as well as the browser.
     *
     * Usage on nodejs
     * ---------------
     *
     *      var instrumenter = new require('istanbul').Instrumenter(),
     *          changed = instrumenter.instrumentSync('function meaningOfLife() { return 42; }', 'filename.js');
     *
     * Usage in a browser
     * ------------------
     *
     * Load `esprima.js`, `escodegen.js` and `instrumenter.js` (this file) using `script` tags or other means.
     *
     * Create an instrumenter object as:
     *
     *      var instrumenter = new Instrumenter(),
     *          changed = instrumenter.instrumentSync('function meaningOfLife() { return 42; }', 'filename.js');
     *
     * Aside from demonstration purposes, it is unclear why you would want to instrument code in a browser.
     *
     * @class Instrumenter
     * @constructor
     * @param {Object} options Optional. Configuration options.
     * @param {String} [options.coverageVariable] the global variable name to use for
     *      tracking coverage. Defaults to `__coverage__`
     * @param {Boolean} [options.embedSource] whether to embed the source code of every
     *      file as an array in the file coverage object for that file. Defaults to `false`
     * @param {Boolean} [options.preserveComments] whether comments should be preserved in the output. Defaults to `false`
     * @param {Boolean} [options.noCompact] emit readable code when set. Defaults to `false`
     * @param {Boolean} [options.noAutoWrap] do not automatically wrap the source in
     *      an anonymous function before covering it. By default, code is wrapped in
     *      an anonymous function before it is parsed. This is done because
     *      some nodejs libraries have `return` statements outside of
     *      a function which is technically invalid Javascript and causes the parser to fail.
     *      This construct, however, works correctly in node since module loading
     *      is done in the context of an anonymous function.
     *
     * Note that the semantics of the code *returned* by the instrumenter does not change in any way.
     * The function wrapper is "unwrapped" before the instrumented code is generated.
     * @param {Object} [options.codeGenerationOptions] an object that is directly passed to the `escodegen`
     *      library as configuration for code generation. The `noCompact` setting is not honored when this
     *      option is specified
     * @param {Boolean} [options.debug] assist in debugging. Currently, the only effect of
     *      setting this option is a pretty-print of the coverage variable. Defaults to `false`
     * @param {Boolean} [options.walkDebug] assist in debugging of the AST walker used by this class.
     *
     */
    function Instrumenter(options) {
        this.opts = options || {
            debug: false,
            walkDebug: false,
            coverageVariable: '__coverage__',
            codeGenerationOptions: undefined,
            noAutoWrap: false,
            noCompact: false,
            embedSource: false,
            preserveComments: false
        };

        this.walker = new Walker({
            ExpressionStatement: this.coverStatement,
            BreakStatement: this.coverStatement,
            ContinueStatement: this.coverStatement,
            DebuggerStatement: this.coverStatement,
            ReturnStatement: this.coverStatement,
            ThrowStatement: this.coverStatement,
            TryStatement: this.coverStatement,
            VariableDeclaration: this.coverStatement,
            IfStatement: [ this.ifBlockConverter, this.coverStatement, this.ifBranchInjector ],
            ForStatement: [ this.skipInit, this.loopBlockConverter, this.coverStatement ],
            ForInStatement: [ this.skipLeft, this.loopBlockConverter, this.coverStatement ],
            WhileStatement: [ this.loopBlockConverter, this.coverStatement ],
            DoWhileStatement: [ this.loopBlockConverter, this.coverStatement ],
            SwitchStatement: [ this.coverStatement, this.switchBranchInjector ],
            SwitchCase: [ this.switchCaseInjector ],
            WithStatement: [ this.withBlockConverter, this.coverStatement ],
            FunctionDeclaration: [ this.coverFunction, this.coverStatement ],
            FunctionExpression: this.coverFunction,
            LabeledStatement: this.coverStatement,
            ConditionalExpression: this.conditionalBranchInjector,
            LogicalExpression: this.logicalExpressionBranchInjector,
            ObjectExpression: this.maybeAddType
        }, this.extractCurrentHint, this, this.opts.walkDebug);

        //unit testing purposes only
        if (this.opts.backdoor && this.opts.backdoor.omitTrackerSuffix) {
            this.omitTrackerSuffix = true;
        }
    }

    Instrumenter.prototype = {
        /**
         * synchronous instrumentation method. Throws when illegal code is passed to it
         * @method instrumentSync
         * @param {String} code the code to be instrumented as a String
         * @param {String} filename Optional. The name of the file from which
         *  the code was read. A temporary filename is generated when not specified.
         *  Not specifying a filename is only useful for unit tests and demonstrations
         *  of this library.
         */
        instrumentSync: function (code, filename) {
            var program;

            //protect from users accidentally passing in a Buffer object instead
            if (typeof code !== 'string') { throw new Error('Code must be string'); }
            if (code.charAt(0) === '#') { //shebang, 'comment' it out, won't affect syntax tree locations for things we care about
                code = '//' + code;
            }
            if (!this.opts.noAutoWrap) {
                code = LEADER_WRAP + code + TRAILER_WRAP;
            }
            program = ESP.parse(code, {
                loc: true,
                range: true,
                tokens: this.opts.preserveComments,
                comment: true
            });
            if (this.opts.preserveComments) {
                program = ESPGEN.attachComments(program, program.comments, program.tokens);
            }
            if (!this.opts.noAutoWrap) {
                program = {
                    type: SYNTAX.Program.name,
                    body: program.body[0].expression.callee.body.body,
                    comments: program.comments
                };
            }
            return this.instrumentASTSync(program, filename, code);
        },
        filterHints: function (comments) {
            var ret = [],
                i,
                comment,
                groups;
            if (!(comments && isArray(comments))) {
                return ret;
            }
            for (i = 0; i < comments.length; i += 1) {
                comment = comments[i];
                /* istanbul ignore else: paranoid check */
                if (comment && comment.value && comment.range && isArray(comment.range)) {
                    groups = String(comment.value).match(COMMENT_RE);
                    if (groups) {
                        ret.push({ type: groups[1], start: comment.range[0], end: comment.range[1] });
                    }
                }
            }
            return ret;
        },
        extractCurrentHint: function (node) {
            if (!node.range) { return; }
            var i = this.currentState.lastHintPosition + 1,
                hints = this.currentState.hints,
                nodeStart = node.range[0],
                hint;
            this.currentState.currentHint = null;
            while (i < hints.length) {
                hint = hints[i];
                if (hint.end < nodeStart) {
                    this.currentState.currentHint = hint;
                    this.currentState.lastHintPosition = i;
                    i += 1;
                } else {
                    break;
                }
            }
        },
        /**
         * synchronous instrumentation method that instruments an AST instead.
         * @method instrumentASTSync
         * @param {String} program the AST to be instrumented
         * @param {String} filename Optional. The name of the file from which
         *  the code was read. A temporary filename is generated when not specified.
         *  Not specifying a filename is only useful for unit tests and demonstrations
         *  of this library.
         *  @param {String} originalCode the original code corresponding to the AST,
         *  used for embedding the source into the coverage object
         */
        instrumentASTSync: function (program, filename, originalCode) {
            var usingStrict = false,
                codegenOptions,
                generated,
                preamble,
                lineCount,
                i;
            filename = filename || String(new Date().getTime()) + '.js';
            this.sourceMap = null;
            this.coverState = {
                path: filename,
                s: {},
                b: {},
                f: {},
                fnMap: {},
                statementMap: {},
                branchMap: {}
            };
            this.currentState = {
                trackerVar: generateTrackerVar(filename, this.omitTrackerSuffix),
            