// narcissus.tree.equal.js
// 
// Copyright (c) 2010 Guillaume Lathoud
// MIT License
// 
// Compare two Narcissus trees (as returned by narcissus.jsparse)

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

from.req('narcissus.tree')('narcissus.tree.equal', function () {
    
    var _EXCLUDED = ['constructor', 'cursor', 'end', 'filename', 'getSource', 'lineno', 'lookahead', 'originalString', 'push', 'scanNewlines', 'scanOperand', 'source', 'start', 'tokenizer', 'tokenIndex', 'tokens', 'top'];

    narcissus.tree.equal = function (/*object*/tree0, /*object*/tree1) {

        var ret = { errors: [], warnings: [], match: false }
        , visited = []

        , sub = function (t0, t1, /*?array?*/stack) {
            
            stack = stack || [];
            stack = stack.concat( { t0: t0, t1: t1} );  // Copy and append

            // Abort at first error

            if (ret.errors.length > 0)
                return;

            // Standard case: compare

            var type0 = typeof t0
            ,   type1 = typeof t1
            ;
            if (type0 !== type1) {
                ret.errors.push( { 
                    message: "Types do not match: " + type0 + " and " + type1
                    , tree0 : tree0
                    , tree1 : tree1
                    , stack : stack
                    , t0 : t0
                    , t1 : t1
                });
                return;
            }

            if (t0 instanceof RegExp) {
                if (!(t1 instanceof RegExp)) {
                    ret.errors.push( { 
                        message: "t0 instanceof RegExp, but not t1"
                        , tree0 : tree0
                        , tree1 : tree1
                        , stack : stack
                        , t0 : t0
                        , t1 : t1
                    });
                    return;
                }
                if (t0.source !== t1.source) {
                    ret.errors.push( { 
                        message: "RegExp t0 and t1 do not match: '" + t0.source + '" and "' + t1.source + '"'
                        , tree0 : tree0
                        , tree1 : tree1
                        , stack : stack
                        , t0 : t0
                        , t1 : t1
                        , source0 : t0.source
                        , source1 : t1.source
                    });
                    return;
                }
                
                return; // success
            }
            
            if (t0 && t1 && (type0 === 'object')) { // non-null objects

                // Prevent infinite loops
                
                if (-1 < array.indexOf( visited, t0 ))
                    return;
                visited.push( t0 );
                
                // Compare keys
                var k0 = object.keys( t0, true )
                ,   k1 = object.keys( t1, true )
                ;

                if (!array.equal( k0, k1 )) {

                    // log('xxx tree0 ' + t0);
                    // log('xxx tree1 ' + t1);

                    ret.errors.push( { 
                        message: "Keys do not match: " + k0 + " and " + k1
                        , tree0 : tree0
                        , tree1 : tree1
                        , stack : stack
                        , t0 : t0
                        , t1 : t1
                        , k0 : k0
                        , k1 : k1
                    });
                    return;
                }
                
                // Compare values
                object.map( t0, function (v, k) { 

                    var cond_0 = number.isFiniteNumber(k)
                    , cond_1 = (k.substring(0, 2) !== '__') && ( 0 > array.indexOf(_EXCLUDED, k) )
                    ;
                    
                    if (cond_0 || cond_1) {
                        
                        var stack2 = [].concat( stack ) // Copy
                        , last = stack2.length - 1
                        ;
                        
                        stack2[ last ] = object.mix( 
                            {},  // Ensure copy
                            stack2[ last ], 
                            { k: k, v: v } // Add information
                        );
                        
                        sub(v, t1[k], stack2); 
                    }

                }, true);
                
                return;
            }

            // Compare nulls, or non-object values (number, string, boolean)

            if (t0 !== t1) {
                ret.errors.push( { 
                    message: "Values do not match: " + t0 + " and " + t1
                    , tree0 : tree0
                    , tree1 : tree1
                    , stack : stack
                    , t0 : t0
                    , t1 : t1
                });
                return;
            }

            // success
        }
        ;

        sub( tree0, tree1 );
        
        ret.match = (ret.errors.length + ret.warnings.length) < 1; 

        return ret;
    };

    //
    
    narcissus.tree.equal.excluded = function () { return [].concat( _EXCLUDED ); /* copy */ };

});