// Copyright (c) 2010 Guillaume Lathoud
// MIT License
/*jslint evil:true */

// The three main functions are:
//
//     tailopt             (calls tailopt_str, then source2fun)
//     tailopt.tailopt_str (returns modified source code strings)
//     tailopt.source2fun  (eval strings to a function)
// 
// To prevent scope issues during the final eval(), we put as much as
// possible under the tailopt.* namespace (a function is an object).
// 
// -----
// Using tailopt.tailopt_str alone
//
// If you do not trust function decompilation:
//
//     Function.prototype.toString
//
// in your target Javascript environment(s) (e.g. mobile), you can
// integrate tailopt.tailopt_str in your Javascript build system,
// and have your server deliver the *already* optimized code.
// 
// -----
// Using tailopt and tailopt.source2fun: scope issues
//
// In your tail recursive function, you should avoid any other closure
// than the tail recursion, because the modified code will most likely
// be eval'ed in a different scope.
//
// In other words, your tail recursive function should be implemented 
// in a scope-independent manner.
//
// Example: in tailopt.tailopt_str we use tailopt.remove_comments (=no
// closure) and not a locally defined remove_comments closure.


// xxx with a parser we could detect closures, inform the user with a
// warning, (or even refuse to optimize the function).  In the future,
// I need to integrate a parser for this reason, and for several
// others (see xxx's below, e.g. variable collision issue).

function tailopt(/* (string | function) fname_or_fun, (function | string) fun_or_head, (string) body*/) {
    //
    // Returns a function
    tailopt.v = {};
    tailopt.v.ret = null;
    
    tailopt.v.o = tailopt.tailopt_str.apply(null, arguments);
    try {
        tailopt.v.ret = tailopt.source2fun(tailopt.v.o.new_source);
    } catch (__tailopt_e__) {
        tailopt.v.ret = null;
    }
    
    if (!tailopt.v.ret) {
        tailopt.error('tailopt() complete failure on ' + tailopt.v.o.orig.head + '.');
        // Try to handle it
        return (typeof arguments[0] === 'function') ? arguments[0] :
            ((typeof arguments[1] === 'function') ? arguments[1] : null); 
    }
    return tailopt.v.ret;   
}

tailopt.source2fun = function(/*string*/__tailopt_source__) {
    // Returns a function.
    //
    // Source is typically a parenthesed function source string like:
    // "(function do_something(with_some, parameters) { /* and a body... */ })"
    
    tailopt.v = {};
    tailopt.v.ret = null;
    try {
        tailopt.v.ret = tailopt.is_not_IE && eval(__tailopt_source__);
    } catch (__tailopt_e__) {
        tailopt.v.ret = null;
        tailopt.error('tailopt.source2fun() caught an exception while working on ' + tailopt.o.orig.head + 
                      ', exception:' + __tailopt_e__);
    }
    
    if (!tailopt.v.ret) {
        try { 
            eval('ret = ' + __tailopt_source__ + ';');
        } catch (__tailopt_e2__) {
            tailopt.v.ret = null;
            tailopt.error('tailopt.source2fun() [fallback, mainly for IE] caught an exception: ' + __tailopt_e2__ + 
                  '\nwhile working on source: ' + __tailopt_source__);
        }
    }
    
    if (!tailopt.v.ret) { throw new Error('tailopt.source2fun() complete failure on source:' + __tailopt_source__); }
    return tailopt.v.ret;
};

tailopt.global   = this;
tailopt.document = this.document;  // undefined if Rhino or V8
// The unavoidable:
tailopt.is_not_IE = !((this.navigator && this.navigator.appVersion && 
                       parseFloat(this.navigator.appVersion.split("MSIE ")[1])) || false);
 
// ----- The rest of the implementation does not impact on the scope
// during the final eval in tailopt.source2fun, so we can use local
// variables again (var declarations and function parameters).

(function () {
    
    var Aps = Array.prototype.slice;

    tailopt.log = function(/*...*/) {
        var f;
        if ((f = tailopt.global.console && tailopt.global.console.log) && f && f.apply) { // Browsers
            f.apply(tailopt.global.console, arguments);

        } else if ((!tailopt.document) && (f = tailopt.global.print) && f && f.apply) { // Rhino, V8
            f.apply(tailopt.global, ["[LOG]"].concat(Aps.apply(arguments)));
        }
    };
    // Comment this to help debug
    tailopt.log = function () {};  

    tailopt.error = function(/*...*/) {
        var f;
        if ((f = tailopt.global.console && tailopt.global.console.log) && f && f.apply) { // Browsers
            f.apply(tailopt.global.console, arguments);

        } else if ((!tailopt.document) && (f = tailopt.global.print) && f && f.apply) { // Rhino, V8
            f.apply(tailopt.global, ["[ERROR]"].concat(Aps.apply(arguments)));
        }
    };

    tailopt.alert = function(s) {
        var f;
        if (tailopt.global.alert) { // Browsers
            tailopt.global.alert(s);

        } else if (!tailopt.document) { // Rhino, V8
            (f = tailopt.global.print) && f && f.call && f.call(tailopt.global, "[ALERT] " + s);
        }
    };

    tailopt.assert = function(/*boolean*/result, /*string*/message) {
        if (tailopt.global.console && tailopt.global.console.assert) {
            tailopt.global.console.assert(result, message);
            return;
        }
        if (!result) {
            tailopt.alert('assert() failure: ' + message);
        }
    };

    function tailopt_str(/* string | function*/ fname_or_fun, /* function | string */ fun_or_head, /*?string?*/ body) {
        //
        // Returns an object containing several strings:
        //         {
        //             new_source: "(" + new_head + "{" + new_body + "})",
        //             new_head: new_head, 
        //             new_body: new_body, 
        //             orig: { 
        //                 fname: fname,
        //                 head:  head,
        //                 body:  body
        //             }        
        //         }
        //
        // Note that tailopt_str itself is tail-recursive :)
        // See an example of application at the very end of this file.

        var fname, arr, rx, mo, s, head, new_head, new_body, o, ret;

        //

        if (typeof fname_or_fun === 'function') {
            return tailopt_str("", fname_or_fun);
        }
        fname = fname_or_fun;

        //

        if (typeof fun_or_head === 'function') {
            if (!(fun_or_head.toSource || fun_or_head.toString)) {
                tailopt.error('Neither function.toSource() nor function.toString() are supported. Returning the function unchanged.');
                return fun_or_head;
            }

            s = fun_or_head.toSource ? fun_or_head.toSource() : fun_or_head.toString();

            rx = /^\s*\(\s*(.*?)\s*\)\s*$/;
            while (mo = rx.exec(s))  s = mo[1];

            rx = /^\s*(function\s*([\w]*?)\s*\([\w\W]*?\))\s*\{([\w\W]*?)\}\s*$/;
            if (!rx.test(s)) {
                tailopt.global.rx = rx;
                tailopt.global.s = s;
                tailopt.log(s);
                tailopt.error('unrecognized function source. Returning the function unchanged. Global vars rx and s may help debugging.');
                return fun_or_head;
            }
            arr = rx.exec(s);
            return tailopt_str(fname || arr[2], arr[1], arr[3]);
        }
        head = fun_or_head;

        //

        try {
            new_head = tailopt.remove_comments(head);
            new_body = tailopt.remove_comments(body);
            new_body = tailopt.unroll_all_namedlets(new_head, new_body);

            if (fname) {
                o = tailopt.try_unroll_top(new_head, new_body, fname);
                new_head = o.head;
                new_body = o.body;
            }

        } catch(e) {            

            tailopt.log('tailopt_str() head:', head);
            tailopt.log('tailopt_str() body.substr(0, 100):', body.substr(0, 100));
            tailopt.error('tailopt_str() is returning the function unmodified because it caught an exception: ' + e);
            
            new_head = head;
            new_body = body;
        }

        return {
            new_source:  "(" + new_head + "{" + new_body + "})",
            new_head: new_head, 
            new_body: new_body, 
            orig: { 
                fname: fname,
                head:  head,
                body:  body
            }
        };
    }
    tailopt.tailopt_str = tailopt_str;

    tailopt.remove_comments = function(s) {

        // xxx Maybe use the one from fun.js
        
        // xxx make this resistant to perverse cases with /* or // within strings or regexps
        // - concretely: we must leave strings and regexp intact
        // - a full JS parser may be needed
        //
        // However for most practical cases the current remove_comments() code should be sufficient!
        
        var a, b, ret = s;

        while (true) {
            a = ret.indexOf('/*');
            b = ret.indexOf('//');

            a = a < 0 ? +Infinity : a;
            b = b < 0 ? +Infinity : b;

            if (! ((a < +Infinity) || (b < +Infinity))) {
                break;
            }
            
            if (a < b) {  // Remove such a comment
                ret = ret.replace(/\/\*[\w\W]*?\*\//, '\n');
            } else { /* Remove such a comment */
                ret = ret.replace(/\/\/[\w\W]*?$/m, '');
            }
            
        }

        return ret;
    };

    tailopt.unroll_all_namedlets = function(head, body) {
        
        var new_body;

        while (true) {
            new_body = unroll_first_namedlet(head, body);
            if (new_body === body) {
                return body;
            }

            tailopt.log('xxx unroll_all_namedlets new body:', new_body);

            body = new_body;
        }
    };

    tailopt.try_unroll_top = function(head, body, fname) {
        
        if (! (head && body && fname)) {
            return;
        }           

        var a, arr = get_vars_from_head(head), 
        tmp_arr, tmp_head, tmp_body,
        new_head, new_body;

        // Maybe the top function itself has a tail call?
        // If yes, we should unroll it. Let us just try.

        tmp_arr = new Array(arr.length);
        for (a = 0; a < arr.length; a++) {
            // xxx again, we should check for variable name collisions,
            // and even avoid it. For now we'll just use improbable variable names.
            tmp_arr[a] = '__0_' + arr[a] + '_0__';
        }
        tmp_head = "function(" + tmp_arr.join(',') + ')';
        tmp_body = "var " + fname + "; return (" + fname + " = function (" + arr.join(',') + "){" + body + "})(" + tmp_arr.join(",") + ");";

        new_head = tmp_head;
        new_body = unroll_first_namedlet(tmp_head, tmp_body);

        if (new_body.substring(new_body.indexOf('{') + 1, new_body.lastIndexOf('}')) !== body) {
            // Success -> return the modified implementation
            return { 
                head: new_head,
                body: new_body
            };
        } else {
            // Failure -> return the original implementation
            return {
                head: head,
                body: body
            };
        }
        
    };

    // ----- The functions below are not accessible through the tailopt.* namespace -----

    function unroll_first_namedlet(head, body) {

        var a, a_rx, arr, b, c, e, block,  blocks, mo, rx_prefix, rx_postfix, rx_tail, new_block, new_block_inner, rx, s, prefix, postfix, vars, new_body;

        // List variables

        vars = get_vars_from_head(head).concat(get_vars_from_body(body));

        tailopt.log("xxx vars:", vars);
        
        // List blocks

        blocks = find_blocks(body);

        // Find the first namedlet

        // xxx in the future, allow () in the prefix and postfix, for now only parenthese-free expressions
        // xxx or: some time in the future, generate an error message for imbricated ()

        // We recognize two forms
        rx = [
            // First form
            {
                prefix:  /\breturn\s*function\s*(\w+)\s*(\([^\(\)]*?\))\s*$/,
                postfix: /^\s*(\([^\(\)]*?\))/
            },
            // First form, with spurious parenthese
            {
                prefix:  /\breturn\s*\(\s*function\s*(\w+)\s*(\([^\(\)]*?\))\s*$/,
                postfix: /^\s*\)\s*(\([^\(\)]*?\))/
            },
            // Second form, with an anonymous function expression
            { 
                prefix:  /\breturn\s*\(\s*(\w+)\s*=\s*function\s*(\([^\(\)]*?\))\s*$/,
                postfix: /^\s*\)\s*(\([^\(\)]*?\))/
            }
        ];
        
        for (a = 0; a < blocks.length; a++) {
            s = blocks[a][0];
            e = blocks[a][1];

            prefix = body.substring(0, s);
            block  = body.substring(s, e+1);
            postfix = body.substring(e+1);

            //         tailopt.log('.');
            //         tailopt.log('xxx prefix', prefix);
            //         tailopt.log('xxx postfix', postfix);
            //         tailopt.log('.');
            
            for ( a_rx = 0; a_rx < rx.length; a_rx++ ) {

                rx_prefix  = rx[a_rx].prefix;
                rx_postfix = rx[a_rx].postfix;

                if ( rx_prefix.test( prefix ) && rx_postfix.test( postfix ) ) {      
                    
                    var mo_prefix = rx_prefix.exec(prefix);
                    var fname = mo_prefix[1];
                    var fpar = get_vars_from_head(mo_prefix[2]);

                    var mo_postfix = rx_postfix.exec(postfix);
                    var fparval = get_vars_from_head(mo_postfix[1]);
                    
                    tailopt.log("xxx named let block: ", body.substring(s, e + 1));
                    tailopt.log("xxx fname:", fname);
                    tailopt.log("xxx fpar:", fpar);
                    tailopt.log("xxx fparval:", fparval);
                    
                    // xxx (maybe at the end) Make sure the variable names will not collide after unrolling
                    // --> if necessary, rename fpar AND variables in block body
                    // --> or at least detect collision and ask the user to rename his variables

                    var label = 'L_' + fname;


                    // Expand recursive conditionals, like:
                    //     return <expr_without_fname> ? <fname>(...) : <something_else>
                    // or:
                    //     return <expr_without_fname> ? <expr_without_fname> : <fname>(...)
                    // or:
                    //     return <expr_without_fname> ? <fname>(...)> : <fname>(...)

                    new_block_inner = expand_recursive_conditionals(block, fname);

                    // xxx some time in the future, generate an error message for imbricated ()
                    rx_tail   = new RegExp('\\breturn\\s+' + fname + '\\s*(\\([^\\(\\)]*\\))\\s*;');
                    tailopt.log("xxx rx_tail.test:", rx_tail.test(new_block_inner));

                    while (rx_tail.test(new_block_inner)) {
                        mo = rx_tail.exec(new_block_inner);
                        var tailval = get_vars_from_head(mo[1]);
                        tailopt.log('xxx tailval:', tailval);

                        var tailrepl = '{ ';
                        for (b = 0; b < tailval.length; b++) {
                            if (tailval[b] !== fpar[b]) {
                                tailrepl += fpar[b] + '_new = ' + tailval[b] + ';\n';
                            }
                        }
                        for (b = 0; b < tailval.length; b++) {
                            if (tailval[b] !== fpar[b]) {
                                tailrepl += fpar[b] + ' = ' + fpar[b] + '_new;\n';
                            }
                        }
                        tailrepl += 'continue ' + label + ';\n}';

                        new_block_inner = new_block_inner.substring(0, mo.index) + 
                            tailrepl + 
                            new_block_inner.substring(mo.index + mo[0].length);

                    }


                    // xxx there is some optimization to do here,
                    // e.g. 
                    //
                    //    str_new = str+str;
                    //    str = str_new;
                    //
                    // should be packed into:
                    //
                    //    str = str + str;
                    //
                    // *when* no other variable update depends on str.
                    //
                    // xxx more generally try to:
                    // - compute the graph of dependencies.
                    // - produce the minimum number of assignments.
                    //
                    // xxx for now, in practice a user obsessed with a
                    // 1 or 2 percents of increased speed is better
                    // off coding the updates herself, e.g. :
                    // 
                    //     str += str;
                    //     return sub(str);
                    //
                    // rather than:
                    //
                    //     return sub(str+str);

                    arr = [];
                    for (b = 0; b < fpar.length; b++) {
                        
                        c = fpar[b];
                        if (fparval[b] !== undefined) {
                            c += ' = ' + fparval[b];
                        }
                        arr.push(c);

                        arr.push(fpar[b] + '_new');
                    }

                    new_block = 'var ' + arr.join(', ') + ';\n';
                    new_block += label + ': while (true) ' + new_block_inner; 

                    tailopt.log('xxx new_block:', new_block);

                    // Put the new block in place

                    new_body = body.substring(0, s - mo_prefix[0].length) + new_block + body.substring(e + 1 + mo_postfix[0].length);


                    tailopt.log('xxx new_body:', new_body);

                    return new_body;  // xxx fix trailing extra ;

                }
            }

        }

        // xxx error message: no tail block found!

        return body;
        
    }

    function get_vars_from_head(head) {
        
        var a, s, ret;

        s = /\(([\w\W]*?)\)/.exec(head)[1].split(',');

        ret = [];
        for (a = 0; a < s.length; a++) {
            ret.push(/^\s*([\w\W]*?)\s*$/.exec(s[a])[1]);
        } 

        return ret;
    }

    function get_vars_from_body(body) {

        // xxx not done yet

        return [];
    }

    function find_blocks(s) {
        
        // Find all '{' and '}', and group them into blocks

        var last = s.length,
        open = -1, close = -1,
        close_arr = [],
        block_arr = [];
        
        while (true) {
            last--;
            if (open < 0) { open  = s.lastIndexOf('{', last); }
            if (close < 0) {  close = s.lastIndexOf('}', last); }
            
            if (open > close) {
                last = open;
                block_arr.push([open, close_arr.pop()]);
                open = -1;
                
            } else if (close > open) {
                last = close;
                close_arr.push(close);
                close = -1;
                
            } else {
                break;
            }
        }
        
        block_arr.reverse();
        return block_arr;
        
    }


    function expand_recursive_conditionals(block, fname) {
        var ret = block,
        rx = /\breturn\s+([^;\?:]+?)\s*\?\s*([^;\?:]+?)\s*:\s*([^;\?:]+?)\s*;/,
        cond, pre, new_cond, post,
        last_index = 0;
        
        // xxx again, in general we would need a full JS parser,
        // however the following should be fine in almost all practical cases.
        
        while (cond = rx.exec(ret.substr(last_index))) {

            tailopt.log("xxx ret.substr(last_index)", ret.substr(last_index), ", cond:", cond);

            if (cond[1].indexOf("return") > -1) {
                last_index += cond.index + "return".length;
                continue;
            }            

            if (cond[1].indexOf(fname) > -1) {

                // Detect mistaken conditionals (not a "named let", and not a tail call)
                
                if (! (new RegExp('^\\s*\\(\\s*' + fname + '\\s*=\\s*')).test(cond[1])) {
                    tailopt.log("expand_recursive_conditionals(): block: ", block);
                    tailopt.log("expand_recursive_conditionals(): fname: ", fname);
                    tailopt.log("expand_recursive_conditionals(): cond: ", cond);
                    throw new Error("expand_recursive_conditionals(block, fname) found a mistake: " +
                                    "to have a tail call, fname must *not* be in the test part of the conditional.");
                }

                // Do not modify irrelevant conditionals
                last_index += cond.index + cond[0].length;
                continue;
            }

            // Do not modify irrelevant conditionals
            
            if ((cond[2].indexOf(fname) < 0) && (cond[3].indexOf(fname)) < 0) {
                last_index += cond.index + cond[0].length;
                continue;
            }

            // Expand relevant conditionals
            
            // xxx permit without { } (this concerns more the "unroll_named_lets" code above)

            pre      = ret.substr(0, last_index + cond.index);
            new_cond = " if(" + cond[1] + "){return " + cond[2] + ";}return " + cond[3] + ";";
            post     = ret.substr(last_index + cond.index + cond[0].length);


            ret        = pre + new_cond + post;
            last_index = last_index + pre.length + new_cond.length;
        }

        return ret;
    }

})();

// ----------------------------------------------------------------------

// Note that tailopt_str is tail-recursive :) 
//
// So just for fun, if you *fully* trust function decompilation
// (Function.prototype.toSource or Function.prototype.toString) on
// your system, then you can uncomment this code line:

// tailopt.tailopt_str = tailopt(tailopt.tailopt_str);

// Note:
// 
// This is incidentally a good debug case for tailopt because the code
// of tailopt_str is relatively long.
//
// This works because tailopt_str does not use any closure:
// e.g. tailopt.remove_comments and not a local closure remove_comments.

// ----------------------------------------------------------------------