// narcissus.tree.scope.js
// 
// Copyright (c) 2010 Guillaume Lathoud
// MIT License
// 
// Walk through a Narcissus tree (as produced by
// ./narcissus.jsparse.js) and produce a list of scopes. For each
// function, a scope is produced, including the list of local variable
// names `locals_here`, and local variable names `locals_parent`
// inherited from the parent scope through closure.
//
// Example of use: ./narcissus.code.compress.js

/*global from log narcissus array number object tool*/

from.req('narcissus.jsdef.js', 'narcissus.tree.js')
('narcissus.tree.scope.js', function () {
    
    var jsdef = narcissus.jsdef;
    
    var me = narcissus.tree.scope = function (toptree) {
        
        // Returns an array of `scope_desc` (scope description), one
        // for each function in the tree.
        //
        // Each `scope_desc` is an object with following fields:
        // {
        //     tree :     <subtree of toptree>  // as produced by `narcissus.jsparse()` (or `jscheck()` wrapper)
        //     , params : <array of string>     // function parameters
        //     , varDecls : <array of subtree>  // function's `varDecls` array, as produced by `narcissus.jsparse()`
        //     , funDecls : <array of subtree>  // function's `funDecls` array, as produced by `narcissus.jsparse()`

        //     , parent_scope : <null | scope_desc object>   // parent scope, if any
        //     , kids         : <array of scope_desc objects>  // kid scopes, if any
        // 
        //     , locals_here :   <array of string>  // local variables declared in this scope
        //     , locals_parent : <array of string>  // `parent_scope.locals` : local variables declared in the parent scopeS (if any)
        //     , locals :        <array of string>  // `locals_here.concat( locals_parent )`
        //
        //     , used_identifiers : <array of string>
        //     , closures :      <array of { name: string, origin_scope : <scope_desc | null> } ]>   // variables used locally and declared in another parent scope
        //
        //     , labels_here :   <array of string>  // local variables declared in this scope
        //     , labels_parent : <array of string>  // `parent_scope.labels` : local variables declared in the parent scopeS (if any)
        //     , labels :        <array of string>  // `labels_here.concat( labels_parent )`
        //
        //     , is_descendant_of : function (other_scope) -> return true iff scope_desc has `other_scope` along its parent chain.
        // }
        //
        // Implementation note: `closures` is computed from `used_identifiers`, `varDecls`, `funDecls` and `parent_scope` recursively.
        
        var scope_ind_stack = []
        , ret
        , f, stacker, filter   // Weak build systems need declaration before use
        ;

        ret = narcissus.tree.walker_gen( f, stacker, filter, { stack_toptree : true } )( toptree );

        function f (tree, acc) 
        {
            var is_fun = (tree.type === jsdef.FUNCTION)
            ,   is_catch = (tree.type === jsdef.CATCH)
            ,   is_label = (tree.type === jsdef.LABEL)
            ,   is_return = (tree.type === jsdef.RETURN)
            ,   is_identifier = (tree.type === jsdef.IDENTIFIER)
            ;

            if (!(is_fun || is_catch || is_label || is_return || is_identifier))
                return;

            if (is_label || is_return || is_identifier) {

                var n = scope_ind_stack && scope_ind_stack.length
                ,   scope_desc = ((n > 0) && acc[ scope_ind_stack[ n-1 ] ]) || null
                ;

                if (!scope_desc)
                    return;

                if (is_label)
                    scope_desc.labels_here.push(tree.label);

                else if (is_return)
                    scope_desc.returns.push(tree);

                else if (is_identifier) {
                    if (!array.has( scope_desc.used_identifiers, tree.value )) {
                        scope_desc.used_identifiers.push( tree.value );
                    }
                }

                else
                    throw new Error('narcissus.tree.scope has a bug.');

                return;
            }
            
            if (is_fun) {

                var scope_desc = { 
                    tree:          tree
                    , params:      tree.params        || []
                    , varDecls:    tree.body.varDecls || []
                    , funDecls:    tree.body.funDecls || [] 
                    , labels_here: []
                    , returns:     []
                    , used_identifiers: [].concat( tree.params )  // copy
                    , kids:        []
                };
                
            } 

            if (is_catch) {

                var scope_desc = {
                    tree:          tree
                    , params:      [ tree.varName ]
                    , varDecls:    []
                    , funDecls:    []
                    , labels_here: []
                    , returns:     []
                    , used_identifiers: [ tree.varName ]
                    , kids:        []
                };

            }
            
            scope_desc.locals_here = scope_desc.params
                .concat( 
                    array.map( scope_desc.varDecls
                               .concat( scope_desc.funDecls )
                               , function (x) { return x.name || ''; } ) );

            // Inherit locals from parent scope (through closure)

            var n = scope_ind_stack && scope_ind_stack.length
            , 
            p     = scope_desc.parent_scope   = ((n > 0) && acc[ scope_ind_stack[ n-1 ] ]) || null // May be `null`
            ;
            if (p)
                p.kids.push( scope_desc );                

            scope_desc.locals_parent  = (scope_desc.parent_scope && scope_desc.parent_scope.locals) || [];

            scope_desc.locals         = scope_desc.locals_here.concat( scope_desc.locals_parent );
            
            // Convenience method

            scope_desc.is_descendant_of = function (ancestor_scope_desc)
            {
                var tmp = scope_desc;
                while (tmp)
                {
                    if (tmp === ancestor_scope_desc)
                        return true;

                    tmp = tmp.parent_scope;
                }
                return ancestor_scope_desc == null;
            } 

            // 

            acc.push( scope_desc );
            
        }

        function stacker (tree, action, acc) 
        {

            var is_fun = (tree.type === jsdef.FUNCTION)
            ,   is_catch = (tree.type === jsdef.CATCH)
            ;

            if (!(is_fun || is_catch))
                return;

            if (action === 'push') {
                var scope_ind = array.indexOf( array.map( acc, function (x) { return x.tree; } ), tree );
                
                if (scope_ind !== acc.length - 1) // Sanity check
                    throw new Error('narcissus.tree.scope: stacker: buggy #0 !'); 
                
                scope_ind_stack.push( scope_ind ); // May be undefined if `scope_ind === -1`

            } else if (action === 'pop') {
                scope_ind_stack.pop();

            } else { // Will never happen
                throw new Error('narcissus.tree.scope: stacker: buggy #1 !');
            }
        }

        function filter (tree, a)
        {

            if (!(tree.type === jsdef.DOT  &&  tree[a].type === jsdef.IDENTIFIER))
                return true;

            return a < 1;  // Filtering necessary for `scope_desc.used_identifiers`
        }
        
        // Compute closures

        for (var n = ret.length; n--; ) {

            var scope_desc = ret[ n ]
            , locals_here  = scope_desc.locals_here
            ;
            scope_desc.closures = [];
            
            array.forEach( scope_desc.used_identifiers
                           , function (name) {

                               if (array.has( locals_here, name )) // Declared locally -> not a closure
                                   return;

                               var origin = null
                               , current  = scope_desc
                               , parent
                               ;

                               while (parent = current.parent_scope) {

                                   current = parent;
                                   if (array.has( current.locals_here, name )) {
                                       origin = current;
                                       break;
                                   }
                               }

                               scope_desc.closures.push( { name : name, origin_scope : /*might be null:*/origin } );
                           });
            
        }

        // 

        return ret;

    };

    // ---
    
    me.detect_var_too_late = function (toptree) {
        
        var scope_arr = me( toptree )
        ,   scope_tree_arr = array.map( scope_arr, function (s) { return s.tree; } )
        ,   ret = []
        ;

        array.map( scope_arr, function (scope) { // One scope at a time

            var scope_var_names = array.map( scope.varDecls, function (x) { return x.name; } );

            narcissus.tree.walker_gen(
                /*f*/function (tree, acc) {

                    if (tree.type !== jsdef.IDENTIFIER)
                        return;

                    var name = tree.value;

                    if (!name)
                        return;

                    if (-1 < array.indexOf( scope.params, name ))
                        return; // Ok

                    // Variable case

                    var ind = array.indexOf( scope_var_names, name )
                    ,   decl = (ind < 0) ? null : scope.varDecls[ ind ]
                    ;
                    
                    if (decl && (tree.start < decl.start)) { // Check
                        ret.push( {
                            message : 'Identifier "' + name + '" used before its declaration. ' + 
                                'This is a valid ECMAScript 3 syntax, but some engines and/or build systems might break.'
                            , cursor : tree.start
                            , tree : tree
                            , decl : decl
                        } );
                    }
                }

                , /*stacker*/null

                , /*filter*/function (tree, a) {
                    
                    if (-1 < array.indexOf( scope_tree_arr, tree[a] )) // One scope at a time
                        return false;

                    if ((tree.type === jsdef.DOT) && (a > 0))
                        return false;

                    if ((tree.type === jsdef.PROPERTY_INIT) && (a < 1))
                        return false;
                    
                    return true;
                }
                

            )( scope.tree );

        });

        return ret;
    };
    
});