// Copyright, 2007, Mats Mattsson

var operatorsString = "[ ] ( ) -> ++ -- += -= *= /= %= <<= >>= &= ^= |= || && == != <= >= << >> > < ~ ! - + & * / % & ^ | ? : = , ; .";
var escapeChars = "*^+[]().|?".split("");
for ( i = 0; i < escapeChars.length; ++i ) {
	operatorsString = operatorsString.replace(new RegExp("(\\"+escapeChars[i]+")","g"),"\\$1"); 
}
var intSuffix = "(((ll|LL|l|L)(u|U)?)|(([uU])(ll|LL|l|L)?))?";
var escapeCode = "(\\\\(u[0-9a-fA-F]{4}|U[0-9a-fA-F]{8}|[ntbrfv\\\\'\"a\\?]|[0-7]{1,3}|[0-9a-fA-F]+))";
var identifier = "[A-Za-z_][A-Za-z0-9_]*";
var literals = new Array(identifier, "(\\d*\\.\\d+|\\d+\\.\\d*)([e|E][+\\-]?\\d+)?[fFlL]?","0[xX]([0-9a-fA-F]*\\.[0-9a-fA-F]+|[0-9a-fA-F]+\\.[0-9a-fA-F]*|[0-9a-fA-F]+)p[+\\-]?\\d+[fFlL]?","0[0-7]+"+intSuffix, "0[xX][0-9a-fA-F]+"+intSuffix,"\\d+"+intSuffix, "L?'("+escapeCode+"|[^'\\\\])+('|$)", "L?\"("+escapeCode+"|[^\"\\\\])+(\"|$)");
var regExps = literals.concat(operatorsString.split(" "));

function Token(name) {
	this.name = name;
}
Token.prototype.str = function () {
	return this.name;
}

function BadToken(name) {}
BadToken.prototype = new Token;

function isIdentifier( s ) {
	return s.match( new RegExp("^" + identifier) );
}


function tokenize( aString ) {
	tokens = [];
	for ( var i = 0; i < aString.length; ++i ) {
		if ( aString.charAt(i) != " " ) {
			var foundToken = false;
			for ( j = 0; j < regExps.length; ++j ) {
				var m = aString.substring(i, aString.length).match( new RegExp( "(^" + regExps[j] + ")" ) );
				if ( m ) {
					i += m[0].length - 1;
					tokens.push( new Token( m[0] ) );
					foundToken = true;
					break;
				}
			}
			if ( ! foundToken ) {
				tokens.push( new BadToken( aString.charAt(i) ));
			}
		}
	}
	return tokens;
}


function Operator(name, type, prec, assoc) {
	this.name = name;
	this.type = type;
	this.prec = prec;
	this.assoc = assoc;
}
Operator.prototype.str = function () {
	return this.name;
}

// types: prefix, postfix, unary, binary, ternary
// assoc: r-t-l, l-t-r
var operators = new Array(
						  new Operator(".",3,16,1),
						  new Operator("->",3,16,1),
						  new Operator("++",1,16,1),
						  new Operator("--",1,16,1),
						  new Operator("++",0,15,0),
						  new Operator("--",0,15,0),
						  new Operator("sizeof",2,15,0),
						  new Operator("~",2,15,-1),
						  new Operator("!",2,15,-1),
						  new Operator("-",2,15,-1),
						  new Operator("+",2,15,-1),
						  new Operator("&",2,15,-1),
						  new Operator("*",2,15,-1),
						  // cast
						  new Operator("*",3,13,1),
						  new Operator("/",3,13,1),
						  new Operator("%",3,13,1),
						  new Operator("+",3,12,1),
						  new Operator("-",3,12,1),
						  new Operator("<<",3,11,1),
						  new Operator(">>",3,11,1),
						  new Operator("<=",3,10,1),
						  new Operator(">=",3,10,1),
						  new Operator("<",3,10,1),
						  new Operator(">",3,10,1),
						  new Operator("!=",3,9,1),
						  new Operator("==",3,9,1),
						  new Operator("&",3,8,1),
						  new Operator("^",3,7,1),
						  new Operator("|",3,6,1),
						  new Operator("&&",3,5,1),
						  new Operator("||",3,4,1),
						  new Operator("?",4,3,0),
						  new Operator("=",3,2,0),
						  new Operator("+=",3,2,0),
						  new Operator("-=",3,2,0),
						  new Operator("*=",3,2,0),
						  new Operator("/=",3,2,0),
						  new Operator("/=",3,2,0),
						  new Operator("/=",3,2,0),
						  new Operator("/=",3,2,0),
						  new Operator(",",3,1,1)
						  );
function FCall (name, par, start, end ) {
	this.name = name;
	this.par = par;
	this.start = start;
	this.end = end;
}
FCall.prototype.str = function () {
	return (this.name ? this.name.str() : "") + this.start + (this.par  ? this.par.str() : "") + this.end;
}

function Node (op, e1, e2, e3, s4) {
	this.op = op;
	this.e1 = e1;
	this.e2 = e2;
	this.e3 = e3;
	this.s4 = s4;
}
Node.prototype.str = function () {
	var s = (this.op ? this.op.str(): "")+"(";
	s+= (this.e1 ? (typeof this.e1 == 'string' ? this.e1 : this.e1.str()) : "" );
	s+= (this.e2 ? " " + this.e2.str() : "" );
	s+= (this.e3 ? " " + this.e3.str() : "" );
	s+= ")";
	return s;
}

function PInfo( n, t ) {
	this.n = n;
	this.t = t;
}

function parseType( tokens ) {
	if ( tokens.length < 1 )
		return new PInfo( null, tokens);
	
	if ( (tokens[0].name == "const" || tokens[0].name == "*" )) {
		var retV = parseType( tokens.slice(1), 0 );
		return new PInfo( retV.n ? new Node( null, tokens[0], retV.n ) : tokens[0], retV.t);
	}
	
	var node;
	if ( tokens.length > 1 && tokens[0].name == "(") {
		var n;
		if ( tokens[1].name == ")" ) {
			n = new Node( null, tokens[0], tokens[1] );
			tokens = tokens.slice(2);
		} else {
			var retV = parseType( tokens.slice(1) );
			if ( retV.t.length < 1 || retV.t[0].name != ")" ) {
				return new PInfo( null, tokens );
			}
			n = retV.n;
			tokens = retV.t.slice(1);
		}

		if ( tokens.length > 1 && tokens[0].name == "(" ) {
			if ( tokens[1].name == ")" ) {
				n = new FCall( n, null, "(", ")" );
				tokens = tokens.slice(2);
			} else {
				var p;
				var retV;
				do {
					tokens = tokens.slice(1);
					retV = parseTypename( tokens );
					if ( retV.n ) {
						p = p ? new Node( null, p, new Token(","), retV.n) : new Node(null, retV.n);
					}
					tokens = retV.t;
				} while ( tokens[0].name == "," );

				if ( retV.t.length > 0 && retV.t[0].name == ")" ) {
					n = new FCall( n, p,  "(", ")" );
				}
				tokens = retV.t.slice(1);
			}
		}
		node = n;
	} else if ( isIdentifier( tokens[0].name) ) {
		node = tokens[0];
		tokens = tokens.slice(1);
	}
		
	while ( tokens.length > 2 && tokens[0].name == "[") {
		if ( tokens[1].name == "]" ) {
			node = new FCall( node, null, "[", "]" );
			tokens = tokens.slice(2);
		} else {
			var retV = parseTokens( tokens.slice(1), 0 );
			if ( retV.t.length > 0 && retV.t[0].name == "]") {
				node = new FCall( node, retV.n, "[", "]" );
				tokens = retV.t.slice(1);
			} else
				break;
		}
	}
	return new PInfo( node, tokens );
}

function parseTypename( tokens ) {
	if ( tokens.length < 1 )
		return new PInfo( null, tokens);
	
	if ( tokens[0].name == "const" ) {
		var retV = parseTypename( tokens.slice(1) );
		return new PInfo( new Node( null, tokens[0], retV.n ), retV.t);
	} else if ( tokens.length > 1 && ( tokens[0].name == "struct" || tokens[0].name == "enum" ) && isIdentifier( tokens[1].name )) {
		var n = new Node( null, tokens[0], tokens[1] )
		tokens = (new Array(n)).concat( tokens.slice(2) );
	} else if ( !isIdentifier( tokens[0].name ) )
		return new PInfo( null, tokens);
	
	if ( tokens.length > 1 ) {
		var retV = parseType( tokens.slice(1), 0 );
		if ( retV.n ) {
			var n = new Node( null, tokens[0], retV.n )
			tokens = (new Array(n)).concat( retV.t );
		}
	}
	
	return new PInfo( tokens[0], tokens.slice(1) );
	
}


function isOperator(t) {
	if ( !(t instanceof Token ) )
		return false;
	for ( var i = 0; i < operators.length; ++i )
		if ( operators[i].name == t.name )
			return true;
	var other = new Array("(", ")", "[", "]");
	for ( var i = 0; i < other.length; ++i )
		if ( other[i] == t.name )
			return true;
	return false;
}
function isLiteral(t) {
	if ( !(t instanceof Token ) )
		return false;
	for ( var i = 0; i < literals.length; ++i )
		if ( t.name.match( new RegExp( "(^" + literals[i] + ")" ) ) )
			return true;
	return false;
}

function parseTokens( tokens, prec ) {

	var foundToken = true;
	while ( foundToken && tokens.length > 0) {
		foundToken = false;
		if ( tokens.length > 0 && (tokens[0] instanceof Token) && tokens[0].name == "(" ) {
			if ( prec <= 14 ) {
				var retVt = parseTypename( tokens.slice(1) );
				if ( retVt.n && retVt.t.length > 0 && retVt.t[0].name == ")") {
					var retV = parseTokens( retVt.t.slice(1), 14 );
					tokens = (new Array( new Node( null, tokens[0], retVt.n, retV.n, ")"))).concat( retV.t );
					foundToken = true;
					continue;
				}
			}
			var retV = parseTokens( tokens.slice(1), 0);
			if ( retV.n && retV.t.length > 0 && (retV.t[0] instanceof Token) && retV.t[0].name == ")" ) {
				tokens = new Array( retV.n );
				if ( retV.t.length > 0 )
					tokens = tokens.concat( retV.t.slice(1) );
				foundToken = true;
				continue;
			}
		}
		var subscript = ["(", ")", "[", "]"];
		for ( var i = 0; prec < 16 && i < 4; i+=2 ) {
			if ( tokens.length > 2 && !isOperator(tokens[0]) && (tokens[1] instanceof Token) && tokens[1].name == subscript[i] ) {
				if ( !i && (tokens[2] instanceof Token) && tokens[2].name == subscript[i+1] ) {
					tokens = new Array( new FCall( tokens[0], null,  subscript[i], subscript[i+1]));
					foundToken = true;
					continue;
				} else {
					var retV = parseTokens( tokens.slice(2), 0);
					if ( retV.n && retV.t.length > 0 && (retV.t[0] instanceof Token) && retV.t[0].name == subscript[i+1] ) {
						tokens = new Array( new FCall( tokens[0], retV.n, subscript[i], subscript[i+1] ));
						if ( retV.t.length > 1 )
							tokens = tokens.concat( retV.t.slice(1) );
						foundToken = true;
						continue;
					}
				}
			}
		}
		
		for ( var i = 0; i < operators.length && prec <= operators[i].prec ; ++i ) {
			switch ( operators[i].type ) {
				case 0:
				case 2:
					if ( tokens.length > 1 && (tokens[0] instanceof Token) && (tokens[0].name == operators[i].name) ) {
						if ( operators[i].name == "sizeof" && tokens[1].name == "(" ) {
							retVt = parseTypename( tokens.slice(2) );
							if ( retVt.n && retVt.t.length > 0 && retVt.t[0].name == ")" ) {
								tokens = new Array( new Node( operators[i], retVt.n)).concat( retVt.t.slice(1) );
								foundToken = true;
							}
						} 
						if ( ! foundToken ) {
							var retV = parseTokens( tokens.slice(1), operators[i].prec + operators[i].assoc);
							if ( retV.n ) {
								tokens = new Array(new Node(operators[i], retV.n)).concat(retV.t);
								foundToken = true;
							}
						}
					}
					break;
				case 1:
					if ( tokens.length > 1 && !isOperator(tokens[0]) && (tokens[1] instanceof Token) && tokens[1].name == operators[i].name ) {
						tokens = new Array(new Node(operators[i], tokens[0])).concat(tokens.slice(2));
						foundToken = true;
					}
					break;
				case 3:
					if ( tokens.length > 2 && !isOperator(tokens[0]) && (tokens[1] instanceof Token) && tokens[1].name == operators[i].name ) {
						var retV = parseTokens( tokens.slice(2), operators[i].prec + operators[i].assoc);
						if ( retV.n ) {
							tokens = new Array(new Node(operators[i], tokens[0], retV.n)).concat(retV.t);
							foundToken = true;
						}
					}
					break;
				case 4:
					if ( tokens.length > 4 && !isOperator(tokens[0]) && (tokens[1] instanceof Token) && tokens[1].name == operators[i].name ) {
						var retV1 = parseTokens( tokens.slice(2), 0);
						if ( retV1.t.length > 1 && (retV1.t[0] instanceof Token) && retV1.t[0].name == ":" ) {
							var retV2 = parseTokens( retV1.t.slice(1), operators[i].prec + operators[i].assoc);
							if ( retV1.n && retV2.n ) {
								tokens = new Array( new Node( operators[i], tokens[0], retV1.n, retV2.n, ":")).concat(retV2.t);
								foundToken = true;
							}
						}
					}
					break;
			}
			if ( foundToken )
				break;
		}
	}

	if ( (tokens[0] instanceof Node) || (tokens[0] instanceof FCall) || isLiteral(tokens[0]) ) {
		return new PInfo( tokens[0], tokens.slice(1) );
	}
	return new PInfo( null, tokens);
}

function parseExpression( str ) {
	var tokens = tokenize( str )
	var retVE = parseTokens( tokens, 0 );
	var retVD = parseTypename( tokens );
	if ( retVD.n && retVE.t.length > 0) {
		retVDe = parseTokens( (new Array( retVD.n )).concat(retVD.t), 0);
		if ( retVDe.t.length < retVE.t.length )
			return retVDe.n;
	}
	return retVE.n;
}