/*------------------------------------------------------------------------------
    This file is part of PHP-AST Project by Romain Gaucher (http://rgaucher.info).

    PHP-AST is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    PHP-AST/ORACLE is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with PHP-AST.  If not, see <http://www.gnu.org/licenses/>.
------------------------------------------------------------------------------*/

#include "AstContainer.h"
#include "Utils.h"
#include "Obfuscator.h"
#include "Translation.h"
#include "Metric.h"
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
#include <stdexcept>
#include <iomanip>
#include <stack>
using namespace std;

string getContent(xmlNode *a_node) {
	xmlChar *c = xmlNodeGetContent(a_node);
	string ret((char *)c);
	utils::replace(ret, "\n","");
	utils::replace(ret, "\r","");
	utils::replace(ret, "\b","");	
	xmlFree(c);
	return ret;
}

ostream& operator<<(ostream& stream, const Ast& ast) {
	kptree::print_tree_bracketed<AstNode>(ast.tr, stream);
	return stream;
}

ostream& operator<<(ostream& stream, const tree<AstNode>& ast){
	kptree::print_tree_bracketed<AstNode>(ast, stream);
	return stream;	
}

ostream& operator<<(ostream& stream, const tree<AstNode>::iterator& iter){
	stream << iter.node;
	return stream;
}

ostream& operator<<(ostream& stream, const VarBase& v) {
	if (v.index.length() < 1)
		stream << v.name;
	else
		stream << v.name << '[' << v.index << ']';
	return stream;
}


void Ast::apply(Obfuscator* obs) {
	obs->operator()(tr, &classes, &variables, &functions);
}

StringBuffer Ast::convert(Translation* obs) {
	clearInfo();
	fillAstInformation();
	return obs->operator()(tr, &classes, &variables, &functions, &assign, &equivalences);
}


MetricResult Ast::compute(Metric *metric) const
{
	return metric->operator()(tr, &classes, &variables, &functions, &assign, &equivalences);
}


/**
	Get the value of the child node wich parent type is 'nodeName'
*/
string Ast::getChildValue(tree<AstNode>::iterator parent, const string& nodeName) const
{
	tree<AstNode>::sibling_iterator children, textable;
	for (children = tr.begin(parent); children != tr.end(parent); ++children){
		if (children->getType() == nodeName) {
			if (tr.number_of_siblings(children) < 1)
				continue;
			textable = tr.begin(children);
			if (textable->getType() == "text")
				return textable->getValue();
		}
	}
	return string();
}


/**
	Calculate the number of nested variables
*/
unsigned Ast::nbNestedVariables(const tree<AstNode>::iterator& iter) const
{
	unsigned nbVars = 0;
	tree<AstNode>::iterator lter = tr.begin(iter);
	for (;lter!=tr.end(iter);++lter) {
		if (lter->getType() == "T_VARIABLE")
			++nbVars;
	}
	return nbVars;
}

void print_current_list(const list<VarBase>& plop) {
	for (list<VarBase>::const_iterator iter = plop.begin(); iter != plop.end(); ++iter)
		cerr << *iter << " | ";
	cerr << endl;
}


/**
	Detect an assignment in the subtree
*/
bool Ast::detectAssignment(const tree<AstNode>::iterator& iter) const
{
	if (tr.number_of_children(iter) == 3 && tr.child(iter, 1)->getType() == "CHAR61")
		return true;
	return false;
}



/**
	Boxing a source code. Get inputs/outputs in term of functions.
*/
void Ast::sourceBoxing(const tree<AstNode>::iterator& it)
{
	// Get the input
	for (tree<AstNode>::iterator iter = tr.begin(it); iter != tr.end(it); ++iter)
	{
		// skip the functions
		if (iter->getType() == "unticked_function_declaration_statement") {
			iter = tr.end(iter);
		}
		else if (detectAssignment(iter))
		{
			// check if the right side has a function, if so, this is an input
			for (tree<AstNode>::iterator jter = tr.begin(iter); jter != tr.end(iter); ++jter) {
				string t = jter->getType();
				if (t == "function_call") {
					tree<AstNode>::iterator son = tr.begin(jter);
					if (son->getType() == "T_STRING") {
						tree<AstNode>::iterator  textable = tr.begin(son);
						if (textable->getType() == "text") {
							if (boxedSource.input.find(textable->getValue()) != boxedSource.input.end())
								continue;
							//cout << "Add in the boxed input ( "<< fctName << " ): " <<  textable->getValue() << endl;
							boxedSource.input.insert(make_pair(textable->getValue(), jter));
						}
					}
				}
				else if (t == "unticked_statement") {
					tree<AstNode>::iterator son = tr.begin(jter);
					if (utils::start_with(son->getType(), "T_")) {
						tree<AstNode>::iterator  textable = tr.begin(son);
						if (textable->getType() == "text") {
							if (boxedSource.input.find(textable->getValue()) != boxedSource.input.end())
								continue;
							//cout << "Add in the boxed input ( "<< fctName << " ): " <<  textable->getValue() << endl;
							boxedSource.input.insert(make_pair(textable->getValue(), jter));
						}
					}
				}
			}
		}
	}

	// Second pass to get the isolated calls, getting the output
	for (tree<AstNode>::iterator iter = tr.begin(it); iter != tr.end(it); ++iter) 
	{
		string t = iter->getType();
		if (t == "unticked_function_declaration_statement") {
			iter = tr.end(iter);
		}
		else if (t == "function_call") {
			tree<AstNode>::iterator son = tr.begin(iter);
			if (son->getType() == "T_STRING") {
				tree<AstNode>::iterator  textable = tr.begin(son);
				if (textable->getType() == "text") {
					if (boxedSource.output.find(textable->getValue()) != boxedSource.output.end())
						continue;
					//cout << "Add in the boxed output ( "<< fctName << " ): " <<  textable->getValue() << endl;
					boxedSource.output.insert(make_pair(textable->getValue(), iter));
				}
			}
		}
		else if (t == "unticked_statement") {
			tree<AstNode>::iterator son = tr.begin(iter);
			if (utils::start_with(son->getType(), "T_")) {
				tree<AstNode>::iterator  textable = tr.begin(son);
				if (textable->getType() == "text") {
					if (boxedSource.output.find(textable->getValue()) != boxedSource.output.end())
						continue;
					//cout << "Add in the boxed output ( "<< fctName << " ): " <<  textable->getValue() << endl;
					boxedSource.output.insert(make_pair(textable->getValue(), iter));
				}
			}
		}
	}
}

/**
	Boxing a function. Get inputs/outputs in term of functions.
*/
void Ast::functionBoxing(const tree<AstNode>::iterator& it, const std::string& fctName)
{
	if (boxedFunction.find(fctName) != boxedFunction.end())
		return;
	else
	{
		BoxedFunction bFct;
		// Get the input
		for (tree<AstNode>::iterator iter = tr.begin(it); iter != tr.end(it); ++iter)
		{
			if (detectAssignment(iter))
			{
				// check if the right side has a function, if so, this is an input
				for (tree<AstNode>::iterator jter = tr.begin(iter); jter != tr.end(iter); ++jter) {
					string t = jter->getType();
					if (t == "function_call") {
						tree<AstNode>::iterator son = tr.begin(jter);
						if (son->getType() == "T_STRING") {
							tree<AstNode>::iterator  textable = tr.begin(son);
							if (textable->getType() == "text") {
								if (bFct.input.find(textable->getValue()) != bFct.input.end())
									continue;
								//cout << "Add in the boxed input ( "<< fctName << " ): " <<  textable->getValue() << endl;
								bFct.input.insert(make_pair(textable->getValue(), jter));
							}
						}
					}
					else if (t == "unticked_statement") {
						tree<AstNode>::iterator son = tr.begin(jter);
						if (utils::start_with(son->getType(), "T_")) {
							tree<AstNode>::iterator  textable = tr.begin(son);
							if (textable->getType() == "text") {
								if (bFct.input.find(textable->getValue()) != bFct.input.end())
									continue;
								//cout << "Add in the boxed input ( "<< fctName << " ): " <<  textable->getValue() << endl;
								bFct.input.insert(make_pair(textable->getValue(), jter));
							}
						}
					}
				}
			}
		}
		// Second pass to get the isolated calls, getting the output
		for (tree<AstNode>::iterator iter = tr.begin(it); iter != tr.end(it); ++iter) 
		{
			string t = iter->getType();
			if (t == "function_call") {
				tree<AstNode>::iterator son = tr.begin(iter);
				if (son->getType() == "T_STRING") {
					tree<AstNode>::iterator  textable = tr.begin(son);
					if (textable->getType() == "text") {
						if (bFct.output.find(textable->getValue()) != bFct.output.end())
							continue;
						//cout << "Add in the boxed output ( "<< fctName << " ): " <<  textable->getValue() << endl;
						bFct.output.insert(make_pair(textable->getValue(), iter));
					}
				}
			}
			else if (t == "unticked_statement") {
				tree<AstNode>::iterator son = tr.begin(iter);
				if (utils::start_with(son->getType(), "T_")) {
					tree<AstNode>::iterator  textable = tr.begin(son);
					if (textable->getType() == "text") {
						if (bFct.output.find(textable->getValue()) != bFct.output.end())
							continue;
						//cout << "Add in the boxed output ( "<< fctName << " ): " <<  textable->getValue() << endl;
						bFct.output.insert(make_pair(textable->getValue(), iter));
					}
				}
			}
		}
		boxedFunction.insert(make_pair(fctName, bFct));
		//cout << "box size = " << boxedFunction.size() << endl;
	}
}

/**
	Mapping one function to others. The other functions are all the function call in
	the function.
*/
void Ast::functionMapping(const tree<AstNode>::iterator& it, const std::string& fctName)
{
	if (fctmap.find(fctName) != fctmap.end())
		return;
	else
	{
		list<string> related;
		for (tree<AstNode>::iterator iter = tr.begin(it); iter != tr.end(it); ++iter) {
			string t = iter->getType();
			if (t == "function_call") {
				tree<AstNode>::iterator son = tr.begin(iter);
				if (son->getType() == "T_STRING") {
					tree<AstNode>::iterator  textable = tr.begin(son);
					if (textable->getType() == "text") {
						related.push_back(textable->getValue());
					}
				}
			}
			else if (t == "unticked_statement") {
				tree<AstNode>::iterator son = tr.begin(iter);
				if (utils::start_with(son->getType(), "T_")) {
					tree<AstNode>::iterator  textable = tr.begin(son);
					if (textable->getType() == "text") {
						related.push_back(textable->getValue());
					}
				}
			}
		}
		// Insert into the fctmap
		fctmap.insert(make_pair(fctName, related));
	}
}


/**
	Get in post-order all the variables
*/
list<VarBase> Ast::getSubVariables(const tree<AstNode>::iterator& it) const
{
	list<VarBase> varBaseList;
	if (nbNestedVariables(it) < 1)
		return varBaseList;
	//cerr << "start:- getSubVars" << endl;
	string type;
	for (tree<AstNode>::iterator iter=tr.begin(it);iter!=tr.end(it) && iter!=tr.end();iter++)
	{
		type = iter->getType();
		//cout << "\t\t\t => type = " << type << endl;
		if (type == "reference_variable")
		{
			//cerr << "\tref_var ";
			unsigned nbchilds = tr.number_of_children(iter);
			//cerr << nbchilds << endl;
			if (nbchilds == 1) {
				//cout << '[' << iter->getType() << " -> " << tr.child(iter,0)->getType()  << ']' << endl;

				if (tr.child(iter, 0)->getType() == "compound_variable") {
					// single variables
					tree<AstNode>::iterator var = iter;
					for(;var->getType() != "text" && var != tr.end(it); ++var)
						;
					//cerr << setw(15) << "ref :- [" << var->getValue() << ',' << it;
					varBaseList.push_back(VarBase(var->getValue(), it));
					//cerr << " ]" << endl;
					iter = var;
				}
			}
			else if (nbchilds == 4) {
				// array ?
				tree<AstNode>::iterator array = tr.child(iter, 0);
				tree<AstNode>::iterator index = tr.child(iter, 2);
				for(;array->getType() != "text" && array != tr.end(it); ++array)
					;
				for(;index->getType() != "text" && index != tr.end(it); ++index)
					;
				//cerr << setw(15) << "array:- [" << array->getValue() << ',' << it << ',' << index->getValue();
				varBaseList.push_back(VarBase(array->getValue(), it, index->getValue()));
				//cerr << " ]" << endl;
				iter = index;
			}
		}
		else if (type == "expr_without_variable" || type == "encaps_var")
		{
			//cerr << "\texpr_wo_var ";
			unsigned nbchilds = tr.number_of_children(iter);
			//cerr << nbchilds << endl;
			for (unsigned c=0;c<nbchilds;++c)
			{
				list<VarBase> varBaseListTemp = getSubVariables(tr.child(iter, c));
				if (varBaseListTemp.size() > 0) {
					// merge the list
					for (list<VarBase>::const_iterator jter=varBaseListTemp.begin();jter!=varBaseListTemp.end();++jter) {
						if (find(varBaseList.begin(),varBaseList.end(),*jter) == varBaseList.end()) {
							//cout << *jter << endl;
							varBaseList.push_back(*jter);
						}
					}
				}
			}
			/*
			// go to the T_VARIABLE
			tree<AstNode>::iterator var = iter;
			for(;var->getType() != "T_VARIABLE" && var != tr.end(it) && var != tr.end(); ++var)
				;
			var = tr.child(var, 0);
			cerr << setw(15) << "expr:- [" << var->getValue() << ',' << it;
			varBaseList.push_back(VarBase(var->getValue(), it));
			cerr << " ]" << endl;
			//iter = var;
			*/
		}
		else if (type == "T_VARIABLE")
		{
			//cout << "TVariable" << endl;
			tree<AstNode>::iterator var = iter;
			for(;var->getType() != "text" && var != tr.end(it); ++var)
				;
			//cerr << setw(15) << "ref :- [" << var->getValue() << ',' << it;
			varBaseList.push_back(VarBase(var->getValue(), it));
			//cerr << " ]" << endl;
			iter = var;
		}
	}
	//cerr << "end:- getSubVars" << endl;
	return varBaseList;
}

/**
	Get in post-order the right variables assignments
*/
list<VarBase> Ast::getRightVariables(const tree<AstNode>::iterator& it, const VarBase& left)
{

	list<VarBase> varBaseList;
	unsigned nestedVars = nbNestedVariables(it);
	if (nestedVars == 0)
		return varBaseList;
	else if (nestedVars == 1 && !detectAssignment(it)) {
		VarBase simple = getSimpleVariable(it);
		varBaseList.push_back(simple);
		return varBaseList;
	}
	else
	{
		// Go to the last right 'expr_without_variable'
		unsigned nbchilds = tr.number_of_children(it);
		tree<AstNode>::iterator iter = tr.child(it, nbchilds - 1);
		//
		if (detectAssignment(iter)) {
			// Assignment => Let's move to the right, and grab the left variable as a 'left variable'
			VarBase leftVar = getLeftVariable(tr.child(iter, 0));
			if (leftVar.name != "")
				varBaseList.push_back(leftVar);
			list<VarBase> rightVars = getRightVariables(tr.child(iter, 2), left);
			// merge the result
			for (list<VarBase>::const_iterator jt=rightVars.begin(); jt!=rightVars.end();++jt)
				varBaseList.push_back(*jt);
		}
		else {
			AstVarBaseList locVarList;
			// get all variables, put that in a equivalences
			for (tree<AstNode>::iterator jter = iter;jter != tr.end(iter); ++jter) {
				string type(jter->getType());
				if (type == "reference_variable")
				{
					unsigned nbchilds = tr.number_of_children(jter);
					if (nbchilds == 1) {
						if (tr.child(jter, 0)->getType() == "compound_variable") {
							// single variables
							tree<AstNode>::iterator var = jter;
							for(;var->getType() != "text"; ++var)
								;
							//cerr << "I got this? " << var->getValue() << endl;
							VarBase right(var->getValue(), it);
							if (!(find(locVarList.begin(), locVarList.end(),right) != locVarList.end()))
								locVarList.push_back(right);
							jter = var;
						}
					}
					else if (nbchilds == 4) {
						// array ?
						tree<AstNode>::iterator array = tr.child(jter, 0);
						tree<AstNode>::iterator index = tr.child(jter, 2);
						for(;array->getType() != "text" && array != tr.end(); ++array)
							;
						for(;index->getType() != "text" && index != tr.end(); ++index)
							;
						VarBase right(array->getValue(), it, index->getValue());
						if (!(find(locVarList.begin(), locVarList.end(),right) != locVarList.end()))
							locVarList.push_back(right);
						jter = index;								
					}
				}
				else if (type == "expr_without_variable")
				{
					//cerr << "expr_wo_var ";
					unsigned nbchilds = tr.number_of_children(iter);
					//cerr << nbchilds << endl;
					for (unsigned c=0;c<nbchilds;++c)
					{
						list<VarBase> varBaseListTemp = getSubVariables(tr.child(iter, c));
						if (varBaseListTemp.size() > 0) {
							// merge the list
							for (list<VarBase>::const_iterator jter=varBaseListTemp.begin();jter!=varBaseListTemp.end();++jter) {
								if (find(locVarList.begin(),locVarList.end(),*jter) == locVarList.end())
									locVarList.push_back(*jter);
							}
						}
					}

				/*
					// go to the T_VARIABLE
					tree<AstNode>::iterator var = jter;
					for(;var->getType() != "T_VARIABLE"; ++var)
						;
					var = tr.child(var, 0);
					//cerr << "I got this? " << var->getValue() << endl;
					VarBase right(var->getValue(), it);
					if (!(find(locVarList.begin(), locVarList.end(),right) != locVarList.end()))
						locVarList.push_back(right);
				*/
				}
			}
			// local equivalences
			equivalences.insert(make_pair(left, locVarList));					
		}
		return varBaseList;
	}
}

/**
	Get a simple variable name; we know that there is one expression with one variable inside.
	We need to get this!
*/
VarBase Ast::getSimpleVariable(const tree<AstNode>::iterator& it)
{
	tree<AstNode>::iterator iter = it;
	// go the the variable
	for (;iter != tr.end(it); ++iter) {
		if (iter->getType() == "reference_variable")
		{
			unsigned nbchilds = tr.number_of_children(iter);
			if (nbchilds == 1) {
				if (tr.child(iter, 0)->getType() == "compound_variable") {
					// single variables
					tree<AstNode>::iterator var = iter;
					for(;var->getType() != "text"; ++var)
						;
					return VarBase(var->getValue(), it);
				}
			}
			else if (nbchilds == 4) {
				// array ?
				tree<AstNode>::iterator array = tr.child(iter, 0);
				tree<AstNode>::iterator index = tr.child(iter, 2);
				for(;array->getType() != "text" && array != tr.end(); ++array)
					;
				for(;index->getType() != "text" && index != tr.end(); ++index)
					;
				return VarBase(array->getValue(), it, index->getValue());
			}
		}
		else if (iter->getType() == "expr_without_variable")
		{
			// go to the T_VARIABLE
			tree<AstNode>::iterator var = iter;
			for(;var->getType() != "T_VARIABLE"; ++var)
				;
			var = tr.child(var, 0);
			return VarBase (var->getValue(), it);
		}
	}
	// backtrack for: strings, functions, class
	return VarBase();
}

/**
	Get left variable name
*/
VarBase Ast::getLeftVariable(const tree<AstNode>::iterator& iter)
{
	tree<AstNode>::iterator it = iter;
	for (;it->getType() != "reference_variable"; ++it)
		;
	unsigned nbchilds = tr.number_of_children(it);
	if (nbchilds == 1) {
		tree<AstNode>::iterator var = it;
		for(;var->getType() != "text"; ++var)
			;
		return VarBase(var->getValue(), it);
	}
	else if (nbchilds == 4) {
		// $foo['var'] pattern detected!
		tree<AstNode>::iterator array = tr.child(it, 0);
		tree<AstNode>::iterator index = tr.child(it, 2);
		for(;array->getType() != "text" && array != tr.end(); ++array)
			;
		for(;index->getType() != "text" && index != tr.end(); ++index)
			;
		return VarBase(array->getValue(), it, index->getValue());
	}
	else {
		// Not supported
		cerr << "getLeftVariable, unsupported elemnts nb = " << *it << endl;
		return VarBase();
	}
	return VarBase();
}

void Ast::fillAstInformation()
{
	tree<AstNode>::iterator iter = tr.begin();
	sourceBoxing(iter);
	tree<AstNode>::sibling_iterator textable;
	tree<AstNode>::fixed_depth_iterator fter = iter;
	for (;iter != tr.end(); ++iter)
	{
		string type = iter->getType();
		if (type == "unticked_class_declaration_statement")
		{	
			string className = getChildValue(iter, "T_STRING");
			if (classes.find(className) != classes.end())
				continue;
			classes.insert(make_pair(className, iter));
		}
		else if (type == "unticked_function_declaration_statement")
		{
			string funcName = getChildValue(iter, "T_STRING");
			if (functions.find(funcName) != functions.end())
				continue;
			functions.insert(make_pair(funcName, iter));
			// Fill the function mapping win this function
			functionMapping(iter, funcName);
			// Get the boxed functions
			functionBoxing(iter, funcName);
		}
		// Variables Names detection
		else if (type == "reference_variable")
		{
			tree<AstNode>::iterator next = iter; ++next;
			if (next->getType() != "compound_variable") {
				// variable with array: $_GET['foo'] => $_GET, [, 'foo', ]
				tree<AstNode>::iterator array = tr.child(iter, 0);
				tree<AstNode>::iterator index = tr.child(iter, 2);
				for(;array->getType() != "text"; ++array)
					;
				for(;index->getType() != "text"; ++index)
					;
				VarBase var(array->getValue(), iter, index->getValue());
				if (!(variables.find(var.name) != variables.end())) {
					AstVarBaseList astFooIterList;
					variables.insert(make_pair(var.name, astFooIterList));
				}
				variables.find(var.name)->second.push_back(var);
			}
		}
		else if (type == "T_VARIABLE")
		{
			textable = tr.begin(iter);
			if (textable->getType() == "text") {
				VarBase var(textable->getValue(), iter);
				if (!(variables.find(var.name) != variables.end())) {
					AstVarBaseList astFooIterList;
					variables.insert(make_pair(var.name, astFooIterList));
				}
				variables.find(var.name)->second.push_back(var);
			}
		}
	}
	for (iter = tr.begin();iter != tr.end(); ++iter) {
		// Assignments, variables relation
		if (detectAssignment(iter))
		{
			VarBase leftVariable = getLeftVariable(tr.child(iter, 0));
			unsigned nbchilds = tr.number_of_children(iter);
			list<VarBase> rightVariables = getRightVariables(tr.child(iter, nbchilds - 1), leftVariable);
			// Store the information
			// for r in rights | reverse:
			//      add ( left <- r )
			//      add (    r <- r + 1 )
			list<VarBase>::reverse_iterator prev = rightVariables.rbegin();
			for (list<VarBase>::reverse_iterator i=rightVariables.rbegin(); i!=rightVariables.rend();++i) {
				// add the link with the left variables
				assign.insert(make_pair(leftVariable, *i));
				if (!(i == rightVariables.rbegin()))
					assign.insert(make_pair(*i, *prev));
				prev = i;
			}
			MapVarEquivalent::iterator rIter;
			for (rIter = equivalences.begin(); rIter != equivalences.end(); ++rIter)
				if (rIter->first == leftVariable) {
					//print_current_list(rIter->second);
				}
			// get the next same_depth iterator since I explored all the children
			tree<AstNode>::fixed_depth_iterator fter = iter;
			iter = ++fter;
		}
	}

}

void Ast::walk(xmlNode *a_node, tree<AstNode>::iterator parent)
{
	xmlNode *cur_node = 0;
	tree<AstNode>::iterator iter = parent;
	for (cur_node = a_node; cur_node; cur_node = cur_node->next) 
	{
		if (cur_node->type == XML_ELEMENT_NODE) {
			string name((char *)cur_node->name);
			iter = tr.append_child(parent,AstNode(name));
		}
		else if (cur_node->type == XML_TEXT_NODE) {
			string content = getContent(cur_node);
			string name((char *)cur_node->name);
			if (content.length() > 0) {
				iter = tr.append_child(parent, AstNode(name, content));
			}
		}
		walk(cur_node->children, iter);
	}
}

Ast::Ast(const string& xmlName)
{
	xmlDoc *doc = 0;
	xmlNode *root_element = 0;
#ifdef xmlReadFile
	doc = xmlReadFile(xmlName.c_str(), 0, 0);
#else
	doc = xmlParseFile(xmlName.c_str());
#endif
	if (doc == 0) {
		cerr << "error: could not parse file :" << xmlName << endl;
	}
	root_element = xmlDocGetRootElement(doc);
	root = tr.begin();
	root = tr.insert(root, AstNode("root"));
	walk(root_element, root);
	xmlFreeDoc(doc);
	xmlCleanupParser();
	fillAstInformation();
}

bool Ast::is_skeleton_node(const tree<AstNode>::iterator& it) const 
{
	string t = it->getType();
	if (t == "T_INLINE_HTML")
		return false;
	else if (t == "text") {
		// look at the parent, if it's T_VARIABLE or T_STRING, keep it
		tree<AstNode>::iterator parent = tr.parent(it);
		string pt = parent->getType();
		if (pt == "T_VARIABLE" || pt == "T_STRING" || pt == "T_CONSTANT_ENCAPSED_STRING")
			return true;
		return false;
	}
	else if ((t == "root" || t == "start" || t == "CHAR61" || t == "expr" || t == "top_statement_list"
	|| t == "internal_functions_in_yacc" || t == "function_call" || t == "statement" || t == "unticked_statement"
	|| utils::start_with(t, "T_")))
		return true;
	return false;
}

bool Ast::detectFunction(const tree<AstNode>::iterator& i) const {
	if (i->getType() == "function_call")
		return true;
	return false;
}


void Ast::trace(const std::string &varName) const
{
	// Find that variables
	AstVarBaseList obsVars, totalVars;
	MapVariables::const_iterator pos=variables.find(varName);
	if (pos != variables.end())
		obsVars = pos->second;
	// check with the assignments to see whether we should look for other variables
	totalVars = obsVars;
	for (MapAssignments::const_iterator iter=assign.begin();iter!=assign.end();++iter) 
	{
		for (AstVarBaseList::iterator jter=totalVars.begin();jter!=totalVars.end();++jter)
		{
			//cerr << "What about?" << iter->second << " , " << *jter << endl;
			if (iter->second.name == jter->name) {
				if (find(totalVars.begin(), totalVars.end(), iter->first) == totalVars.end())
					totalVars.push_back(iter->first);				
			}
		}
	}
	print_current_list(totalVars);
	// For each variable in the domain, look for the functions, calls etc.
	for (AstVarBaseList::iterator iter=totalVars.begin(); iter!=totalVars.end();++iter) {
		cerr << *iter << endl;
		// take this variable and rewind it!
		tree<AstNode>::iterator	nter = iter->position;
		do {
			nter = tr.parent(nter);
			// Check for functions
			if (detectFunction(nter)) {
				cerr << nter << endl;
			}
		} while (nter != tr.begin());			
	}
}

Ast Ast::skeleton() const
{
	Ast temp(*this);
	temp.ref = const_cast<Ast *>(this);
	for (tree<AstNode>::iterator iter=temp.tr.begin(); iter!=temp.tr.end();++iter)
	{
		if (!temp.is_skeleton_node(iter)) {
			// just delete it with reparent
			temp.tr.reparent(temp.tr.parent(iter), iter);
		}
	}
	return temp;	
}


void Ast::printInfo(ostream& stream) const
{
	stream << "-- Ast Information --" << endl;
	stream << "Functions:" << endl;
	for (MapFunctions::const_iterator iter = functions.begin(); iter != functions.end(); ++iter) {
		stream << '\t' << iter->first << '|' << iter->second->getType() << endl;
	}
	stream << "Classes:" << endl;
	for (MapClasses::const_iterator iter = classes.begin(); iter != classes.end(); ++iter) {
		stream << '\t' << iter->first << '|' << iter->second->getType() << endl;
	}
	stream << "Variables:" << endl;
	for (MapVariables::const_iterator iter = variables.begin(); iter != variables.end(); ++iter) {
		stream << setw(10) << iter->first << endl;
	}
	stream << "Assignments:" << endl;
	for (MapAssignments::const_iterator iter = assign.begin(); iter != assign.end(); ++iter) {
		stream << '\t' << iter->first << " <-- " << iter->second << endl;
	}
	
	stream << "Equivalences:" << endl;
	for (MapVarEquivalent::const_iterator iter = equivalences.begin(); iter != equivalences.end(); ++iter)
	{
		stream << setw(10) << iter->first << ": \t";
		for (AstVarBaseList::const_iterator jter=iter->second.begin(); jter!=iter->second.end();++jter)
			stream << *jter << ", ";
		stream << endl;
	}
}

void Ast::clearInfo()
{
	classes = MapClasses();
	variables = MapVariables();
	functions = MapFunctions();
}

string htmlentities(const string& str)
{
	string ret;
	for(string::const_iterator iter=str.begin();iter!=str.end();++iter) {
		switch (*iter) {
			case '&' : ret += "&amp;"; break;
			case '<' : ret += "&lt;"; break;
			case '>' : ret += "&gt;"; break;
			case '"' : ret += "&quot;"; break;
			default: ret += *iter; break;
		}
	}
	return ret;
}

void writeSiblingsXML(const tree<AstNode>& t, const tree<AstNode>::iterator iRoot, ostream& stream)
{
	if(t.empty()) 
		return;
	if (iRoot->getType() == "root") {
		tree<AstNode>::sibling_iterator iChildren = t.begin(iRoot);
		stream << "<?xml version=\"1.0\" encoding=\"UTF-8\" ?>" << endl;
		writeSiblingsXML(t,iChildren,stream);
	}
	else if (t.number_of_children(iRoot) == 0) {
		string type = iRoot->getType();
		stream << "<php:" << type << '>';
		if (iRoot->getValue().length() > 0)
			stream << htmlentities(iRoot->getValue());
		stream << "</php:" << type << '>' << endl;
	}
	else {
		string type = iRoot->getType();
		string xmlns="";
		if (type == "start")
			xmlns = " xmlns:php=\"http://php.net/csl\"";
		stream << "<php:" << type << xmlns << '>' << endl;
		int siblingNum;
		tree<AstNode>::sibling_iterator iChildren;
		for (iChildren = t.begin(iRoot), siblingNum = 0; iChildren != t.end(iRoot); ++iChildren) 
		{
			writeSiblingsXML(t,iChildren,stream);
		}
		stream << "</php:" << type << '>' << endl;
	}
}

void exportXML(const Ast& ast, const string& xmlName)
{
	if (ast.tr.empty()) {
		throw length_error("AstContainer::exportXML - The AST is empty");
		return;
	}
	ofstream stream(xmlName.c_str());
	if (!stream.is_open())
		return;
	// skip <root>
	for(tree<AstNode>::sibling_iterator iRoots = ast.tr.begin(); iRoots != ast.tr.end(); iRoots++) {
		writeSiblingsXML(ast.tr,iRoots,stream);
	}
	stream.close();
}
