// narcissus.tree.js
// Tools to analyze the tree returned by narcissus.jsparse
// 
// Copyright (c) 2010 Guillaume Lathoud
// MIT License

/*global from log narcissus array tool*/

from.req( 'narcissus.jsparse.js', 'tool.code.js', 'tool.text.js', 'array.js' )('narcissus.tree', function () {
    
    var detect_extra_comma, detect_extra_comma_in_fun_params, detect_undeclared_global, detect_global, detect_global_names;
    var detect_declaration_repetition, detect_missing_semicolon, is_descendant, node_end, source;
    var _column_no, _line_no, _line_to, _next_after_comments;

    (function (_tree_walker_gen /*implemented further below*/) {

        narcissus.tree.detect_extra_comma = detect_extra_comma = _tree_walker_gen( function (tree, acc) {
            if ((tree.type === narcissus.jsdef.ARRAY_INIT) || (tree.type === narcissus.jsdef.OBJECT_INIT)) {
                var s = source( tree ),
                
                closer = _next_after_comments(
                    s, 
                    (tree.type === narcissus.jsdef.ARRAY_INIT) ? ']' : '}', 
                    tree.end 
                ),
                
                comma = ((closer > -1) && _next_after_comments( s, ',', tree.end, closer)) || -1
                
                ;
                
                if (comma > -1) {
                    acc.push( 
                        {
                            message : 'Extra comma detected at line ' + _line_no(s, comma) +
                                ', column ' + _column_no(s, comma) +
                                ' (cursor ' + comma + '). IE6 and IE7 will break down on this!',
                            cursor: comma
                        }
                    );
                }
                
            }
            
        });

        narcissus.tree.detect_extra_comma_in_fun_params = detect_extra_comma_in_fun_params = _tree_walker_gen( function (tree, acc) {

            if (! ( (tree.type === narcissus.jsdef.FUNCTION) && tree.params && tree.body))
                return;
            
            var s = source( tree )
            ,   comma_arr  = []
            ,   cursor     = tree.start
            ,   cursor_end = tree.body.start
            ,   next
            ;
            
            next       = (function (j) { 
                return function (str, cursor, /*?boolean?*/not_expected) {

                    var ret  = _next_after_comments( s, str, cursor, cursor_end );

                    log.assert( (ret > -1) ^ not_expected, 
                                "narcissus.tree.detect_extra_comma_in_fun_params has a bug (#" + j + ", str: '" +
                                str + "' ), not_expected: " + not_expected );
                    
                    j++;
                    return ret;
                };
            })( 1 );

            
            cursor = next( 'function', cursor, s.slice(cursor) ) + 'function'.length;
            
            if (tree.name)
                cursor = next( tree.name, cursor ) + tree.name.length;

            cursor = next( '(', cursor ) + 1;

            for ( var a = 0; a < tree.params.length; a++ ) {
                cursor = next( tree.params[a], cursor ) + tree.params[a].length;
            }

            var rx = /\S+/;
            cursor = next( rx, cursor );

            if ((cursor > -1) && (s.charAt( cursor ) === ')'))
                return; // Correct

            // Incorrect: e.g. at least one extra comma
            var wrong = s.substring( cursor ).match( rx )[0]
            ;

            if (wrong.charAt( 0 ) === ',') // Not expecting anything other than an extra comma...
                wrong = ',';

            if (wrong.length > 100)  // ...but let us stay open.
                wrong = wrong.substring(0, 100) + '...';

            acc.push(
                {
                    message : 'Unexpected "' + wrong + '" after function parameters' +
                        ' - line ' + 
                        _line_no(s, cursor) +
                        ', column ' + _column_no(s, cursor) +
                        ' (cursor ' + cursor + ').',
                    cursor : cursor
                }
            );
            
        });
        
        narcissus.tree.detect_undeclared_global = detect_undeclared_global = function (tree) {

            var arr = detect_global(tree),
            s = source( tree ),
            arr_decl, a,
            ret = []
            ;

            // Yes, `undefined` is a global variable. Try this:
            // 
            // >>> undefined = 4; console.log(undefined); var b; console.log(b); console.log(b === undefined);
            // 4
            // undefined
            // false
            arr_decl = [
                'Array'
                , 'Boolean', 'Date', 'Error', 'Function', 'Infinity'
                , 'Math', 'NaN', 'Number', 'Object', 'RegExp', 'String', 'SyntaxError'
                , 'arguments', 'decodeURI', 'decodeURIComponent', 'encodeURI'
                , 'encodeURIComponent', 'escape', 'eval', 'isFinite'
                , 'isNaN', 'isNumber', 'parseFloat', 'parseInt'
                , 'undefined', 'unescape'
            ]
                .concat( (/\/\*global\s([^\*]+?)\*\//.exec(s) || ['',''])[1].split(/[\s\n\r\t,]/) )
                .concat( (s.match(/\/\*global\*\/[\w-_]+/g) || []).join(' ').replace(/\/\*global\*\//g, '').split(/ /g))
                .concat( (s.match(/\/\*global\*\/\s*function\s+([\w-_]+)/g) || []).join(' ')
                         .replace(/\(\/\*global\*\/|function\)/g, '').split(/ /g))
            ;
            
            for (a = 0; a < arr.length; a++) {

                var is_ident = (arr[a].type === narcissus.jsdef.IDENTIFIER);

                if (array.indexOf(arr_decl, is_ident ? arr[a].value : arr[a].name) > -1)
                    continue
                ;

                var node = arr[a];
                ret.push(
                    {
                        message : 'Undeclared global ' +
                            ( is_ident ? ( 'variable "' + node.value + '"' ) : ( 'function "' + node.name + '"' ) ) +
                            ' detected at line ' + _line_no(s, node.start) +
                            ', column ' + _column_no(s, node.start) + ' (cursor ' + node.start + '). This might be a typo.',
                        cursor: node.start
                    }
                );
            }

            return ret;
        };

        narcissus.tree.detect_global = detect_global = function (toptree) {

            // Returns: an array of object (narcissus tree nodes).
            //
            // If you only want an array of string (global variable
            // and function names), use:
            // `narcissus.tree.detect_global_names`.

            var filter, stacker, walker_f, _stack = [], _stack_flat = [];

            filter = function (tree, k) {

                if ((tree.type === narcissus.jsdef.FUNCTION) && (-1 < array.indexOf(toptree.funDecls, tree)))
                    return true;

                return !(
                    ((tree.type === narcissus.jsdef.PROPERTY_INIT) && (k == 0) && (tree[k].type === narcissus.jsdef.IDENTIFIER)) 
                        ||
                        ((tree.type === narcissus.jsdef.DOT) && (parseInt(k, 10) > 0))                                              
                );
            };
            
            stacker = function (tree, action) {

                var a, n, arr;

                if (action === 'pop') {
                    n = _stack.pop().length;
                    _stack_flat.splice( _stack_flat.length - n, n );
                    return;
                }
                if (action !== 'push') {
                    throw new Error('narcissus.tree.detect_global: stacker bug.');
                }

                arr = [];

                if ((tree.type === narcissus.jsdef.FUNCTION) && tree.params) {
                    arr = arr.concat( tree.params );
                }
                if ((tree.type === narcissus.jsdef.CATCH) && tree.varName) {
                    arr = arr.concat( tree.varName );
                }
                if (tree.varDecls) {
                    for (a = 0; a < tree.varDecls.length; a++) {
                        arr.push( tree.varDecls[a].name );
                    }
                }
                if (tree.funDecls) {
                    for (a = 0; a < tree.funDecls.length; a++) {
                        arr.push( tree.funDecls[a].name );
                    }
                }

                _stack.push( arr );
                _stack_flat = _stack_flat.concat( arr );

            };

            walker_f = function (tree, acc) {
                if (tree.type === narcissus.jsdef.IDENTIFIER) {
                    if ((-1 < array.indexOf( toptree.varDecls, tree )) || (array.indexOf( _stack_flat, tree.value ) < 0)) {
                        acc.push( tree );
                        return;
                    }
                }

                if ( (tree.type === narcissus.jsdef.FUNCTION) && (-1 < array.indexOf( toptree.funDecls, tree ))) {
                    acc.push(tree);
                    return;
                }
            };
            
            return _tree_walker_gen( walker_f, stacker, filter )( toptree );
        };

        narcissus.tree.detect_global_names = detect_global_names = function (tree) {
            
            return array.map( detect_global( tree ), function (node) { 

                return (node.type === narcissus.jsdef.IDENTIFIER) ? node.value : node.name;

            });
            
        };
        
        narcissus.tree.detect_declaration_repetition = detect_declaration_repetition = _tree_walker_gen( function (tree, acc) {

            var a, s, varDecls, varnode, varname;

            if (! ( (tree.type === narcissus.jsdef.FUNCTION) && tree.params && tree.body && (varDecls = tree.body.varDecls)))
                return
            ;
            
            for (a = 0; a < varDecls.length; a++) {

                varnode = varDecls[a];
                varname = varnode.name;

                if (array.indexOf( tree.params, varname ) > -1) {
                    s = s || source( tree );
                    acc.push(
                        {
                            message : 'Variable "' + varname + '" already declared as parameter of function "' + tree.name + '"' +
                                ' - line ' + 
                                _line_no(s, varnode.start) +
                                ', column ' + _column_no(s, varnode.start) +
                                ' (cursor ' + varnode.start + ').',
                            cursor : varnode.start
                        }
                    );
                }
            }
        });

        narcissus.tree.detect_missing_semicolon = detect_missing_semicolon = function (tree) {

            var function_stack = [];
            
            var f = function (tree, acc) {

                if (0 > array.indexOf( [ narcissus.jsdef.SEMICOLON, narcissus.jsdef.VAR ], tree.type ))
                    return
                ;
                
                var s   = source( tree )
		, start = node_end( tree )
                , end   = (function_stack.length > 0) ? function_stack[ function_stack.length - 1 ] : s.length
                ;
		
                if (-1 < _next_after_comments( s, ';', start, end ))
                    return;  // Correct
                
                // Incorrect
                acc.push( {
                    message : 'Missing semicolon' + ' - line ' +
                        _line_no(s, start) +
                        ', column ' + _column_no(s, start) +
                        ' (cursor ' + start + '). Piece: "' + s.substring( tree.end, start ) + '"',
                    cursor : start
                }
                        );
            };

            var stacker = function (tree, action, acc) {
                if (tree.type !== narcissus.jsdef.FUNCTION)
                    return;
                
                if (action === 'push')
                    function_stack.push(node_end(tree));
                else if (action === 'pop')
                    function_stack.pop();

            };

            return _tree_walker_gen(f, stacker)( tree );
        };

        narcissus.tree.is_descendant = is_descendant = function ( candidate, ancestor ) {

            var found = false
            , walker  = _tree_walker_gen(
                function /*f*/(tree) 
                {
                    if (tree === candidate)
                        found = true;
                }
                , /*stacker*/null
                , /*filter*/function () 
                {
                    return !found; // Stop the search as soon as we found it
                }
            )
            ;
            
            walker( ancestor );
            
            return found;
            
        };

	narcissus.tree.node_end = node_end = function ( tree ) {

	    var end = tree.end;

	    if (typeof end !== 'number')
		return source(tree).length;  // Typically top-level script

	    _tree_walker_gen( /*f*/ function ( subtree ) { 
		if (typeof (subtree && subtree.end) !== 'number')
		    return;
		end = Math.max( end, subtree.end ); 
	    })( tree );

	    return end;
	};

        narcissus.tree.source = source = function( tree ) {
            return tree.tokenizer.source;
        };

        // 

        _column_no = tool.text.column_no;

        _line_no = tool.text.line_no;

        _line_to = tool.text.line_to;

        _next_after_comments = tool.code.next_after_comments;
        
    })(/*_tree_walker_gen: Tree walker generator*/
        
        narcissus.tree.walker_gen = 
            
        function ( f/*:function (tree, acc)*/, /*?function?*/stacker, /*?function?*/filter, /*?object?*/opts ) {
            
            opts = opts || {};

	    var visited = {/* <number:start> : <array of tree nodes>*/}
	    , is_visited = function ( tree ) {
		
		if (!tree)
		    return false;
		
		var start = tree.start || 0;
		
		return visited[start] && (-1 < array.indexOf( visited[start], tree ));
	    }
	    , mark_visited = function ( tree ) {

		if (!tree)
		    return;

		if (is_visited(tree))
		    return;

		var start = tree.start || 0;
		
		(visited[start] = visited[start] || []).push( tree );
	    }
	    ;

            return /*tree walker:*/ function ( toptree ) 
            {
                var acc = acc || [] // Will be returned through `ret`
                , ret 
                , sub // Weak build systems need declaration before use
                ;
                
                if (opts && opts.stack_toptree)  // See `narcissus.tree.scope` for an example of use.
                    stacker( toptree, 'push', acc );

		ret = sub( toptree ); 

                if (opts && opts.stack_toptree)
                    stacker( toptree, 'pop', acc );

	        return ret;

                //
                
                function sub ( tree, /*?number?*/timestamp )
                {
                    if (!(tree && (tree instanceof Array)))
                        return acc;
                    
                    timestamp = timestamp || ( (new Date()).getTime() + Math.random());
                    
                    if (is_visited( tree ))
		        return acc;
		    mark_visited( tree );
		    
                    f(tree, acc);
                    
                    if (stacker) 
                        stacker( tree, 'push', acc );
                    
                    for (var a = 0; a < tree.length; a++) 
                    {
                        if (!tree[a])
                            continue
                        ;
                        if ( (!filter) || filter( tree, a ) )
                            sub(tree[a], timestamp)
                        ;
                    }
                    for (var s in tree) 
                    {
                        if (!tree[s])
                            continue
                        ;
                        if ( (!filter) || filter( tree, s ) )
                            sub(tree[s], timestamp)
                        ;
                    }
                    if (stacker) 
                        stacker( tree, 'pop', acc );
                    
                    return acc;
                }
            };
            
        }
    );
    
});