meridiandsl.cpp

件主要用于帮助计算机爱好者学习蚁群算法时做有关蚁群算法的试验。蚁群算法作为一种优秀的新兴的算法

/******************************************************************************
Meridian prototype distribution
Copyright (C) 2005 Bernard Wong

This program 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 2
of the License, or (at your option) any later version.

This program 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 this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

The copyright owner can be contacted by e-mail at [e-mail]
*******************************************************************************/

using namespace std;

#include <stdio.h>
#include <stdlib.h>
#include <ucontext.h>
#include <stdint.h>
#include <rpc/rpc.h>
#include <unistd.h>
#include <sys/socket.h>
#include <netdb.h>
#include <errno.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <zlib.h>
#include <float.h>
#include <math.h>
#include "Marshal.h"
#include "MQLState.h"
#include "MeridianDSL.h"

template <class T>
T opr(int op, T param_1, T param_2) {
	switch(op) {
		case '*':
			return (param_1 * param_2);
		case '+':
			return (param_1 + param_2);
		case '-':
			return (param_1 - param_2);	
		case '/':
			return (param_1 / param_2);			
	}
	return 0;
}

template <class T>
int opr_int_ret(int op, T param_1, T param_2) {
	switch(op) {
		case AND_OP:
			return (param_1 && param_2);
		case OR_OP:
			return (param_1 || param_2);	
		case '<':
			return (param_1 < param_2);
		case '>':
			return (param_1 > param_2);
		case LE_OP:
			return (param_1 <= param_2);
		case GE_OP:
			return (param_1 >= param_2);
		case EQ_OP:
			return (param_1 == param_2);
		case NE_OP:
			return (param_1 != param_2);
	}
	return 0;
}

int opr_int_only(int op, int param_1, int param_2) {
	switch(op) {
		case '|':
			return (param_1 | param_2);
		case '&':
			return (param_1 & param_2);
		case '^':
			return (param_1 ^ param_2);
		case LEFT_OP:
			return (param_1 << param_2);
		case RIGHT_OP:
			return (param_1 >> param_2);
	}
	return 0;
}

int marshal_packet(ParserState* ps, RealPacket& inPacket,
		const string* func_name, const ASTNode* paramAST) {
#if 0			
	ASTNode* funcVar = NULL; 
	if (ps->get_var_table()->lookup(*(func_name), &funcVar) == -1) {
		DSL_ERROR("Function name %s not found\n", func_name->c_str());
		return -1;
	}
#endif	
	//	Allocate compression buffer
	uLongf tmpCompBufSize = (2 * ps->input_buffer.get_buf_size()) + 12;
	char* tmpCompBuf = (char*) malloc(tmpCompBufSize);
	if (tmpCompBuf == NULL) {
		DSL_ERROR("Cannot allocate temporary compress buffer\n");
		return -1;	
	}
	if (compress((Bytef*)tmpCompBuf, (uLongf*)&tmpCompBufSize,
			(Bytef*)ps->input_buffer.get_raw_buf(), 
			ps->input_buffer.get_buf_size()) != Z_OK) {
		DSL_ERROR("zlib compression failed\n");
		free(tmpCompBuf);
		return -1;
	}
	//	This packet MUST not have a rendavous host
	// 	Save both original size and compressed size
	inPacket.append_uint(htonl(ps->input_buffer.get_buf_size()));
	inPacket.append_uint(htonl(tmpCompBufSize));			
	inPacket.append_str(tmpCompBuf, tmpCompBufSize);
	free(tmpCompBuf); // Done with compress buffer
	inPacket.append_uint(htonl(func_name->size()));
	inPacket.append_str(func_name->c_str(), func_name->size());
	if (!(inPacket.completeOkay())) {
		DSL_ERROR("Packet creation failure\n");
		return -1;	
	}			
	if (marshal_ast(paramAST, &inPacket) == -1) {
		return -1;
	}
	return 0;
}

ASTNode* arith_operation(ParserState* cur_parser, int op,  
		const ASTNode* a, const ASTNode* b) {
	ASTNode* retVar = cur_parser->get_var_table()->new_stack_ast();
	if (retVar == NULL) {
		return cur_parser->empty_token();	
	}
	if (a->type != INT_TYPE && b->type != DOUBLE_TYPE) {
		DSL_ERROR(
			"Cannot perform arith operation on non int/double type\n");					
		return cur_parser->empty_token();
	}
	if (a->type != b->type) {
		DSL_ERROR("Arith operation on incompatible types\n");
		return cur_parser->empty_token();
	}
	switch (op) {	
	case '%':
		// Special treatement of floats
		switch((retVar->type = a->type)) {
			case INT_TYPE:
				retVar->val.i_val = a->val.i_val % b->val.i_val;
				break;
			case DOUBLE_TYPE:
				retVar->val.d_val = fmod(a->val.d_val, b->val.d_val);
				break;
			default:
				DSL_ERROR("Unknown type encountered (parser error)\n");
				return cur_parser->empty_token();
		}
		break;
	case '&':
	case '^':
	case '|':
	case LEFT_OP:
	case RIGHT_OP:
		// Operates on ints only
		if ((retVar->type = a->type) != INT_TYPE) {
			DSL_ERROR("Cannot operate on double\n");
			return cur_parser->empty_token();			
		}
		retVar->val.i_val = opr_int_only(op, a->val.i_val, b->val.i_val);
		break;
	case AND_OP:
	case OR_OP:
	case '<':
	case '>':
	case LE_OP:
	case GE_OP:
	case EQ_OP:
	case NE_OP:
		// Returns ints only
		retVar->type = INT_TYPE;
		switch (a->type) {
			case INT_TYPE:
				retVar->val.i_val = 
					opr_int_ret<int>(op, a->val.i_val, b->val.i_val);
				break;
			case DOUBLE_TYPE:
				retVar->val.i_val = 
					opr_int_ret<double>(op, a->val.d_val, b->val.d_val);
				break;
			default:
				DSL_ERROR("Unknown type encountered (parser error)\n");
				return cur_parser->empty_token();				
		}		
		break;			
	default:
		switch((retVar->type = a->type)) {
			case INT_TYPE:
				retVar->val.i_val 
					= opr<int>(op, a->val.i_val, b->val.i_val);
				break;
			case DOUBLE_TYPE:
				retVar->val.d_val 
					= opr<double>(op, a->val.d_val, b->val.d_val);
				break;
			default:
				DSL_ERROR("Unknown type encountered (parser error)\n");
				return cur_parser->empty_token();
		}
		break;
	}
	return retVar;
}

ASTNode* ASTCreate(ParserState* cur_parser, const ASTType in_type, 
		const string* adt_name, const ASTType array_type, int array_size) {
	ASTNode* retNode = cur_parser->get_var_table()->ASTCreate(in_type, 
		adt_name, array_type, array_size);
	if (retNode == NULL) {
		return cur_parser->empty_token();
	}
	return retNode;
}

ASTNode* ADTCreateAndCopy(ParserState* ps, const ASTNode* a) {
	switch (a->type) {
		case ARRAY_TYPE: {
			DSL_ERROR("ADTCreateAndCopy currently "
				"does not support array types\n");
			return ps->empty_token();
		}
		case INT_TYPE:
		case DOUBLE_TYPE:
		case STRING_TYPE: {
			ASTNode* tmpNode = ASTCreate(ps, a->type, NULL, VOID_TYPE, 0);
			if (tmpNode->type == EMPTY_TYPE) {
				return ps->empty_token();
			}
			if (ps->get_var_table()->updateADT(tmpNode, a) == -1) {
				return ps->empty_token();
			}
			return tmpNode;				
		}
		case VAR_ADT_TYPE: {
			ASTNode* tmpNode = ASTCreate(ps, ADT_TYPE, 
				a->val.adt_val.adt_type_name, VOID_TYPE, 0);
			if (tmpNode->type == EMPTY_TYPE) {
				return ps->empty_token();
			}
			if (ps->get_var_table()->updateADT(tmpNode, a) == -1) {
				return ps->empty_token();
			}
			return tmpNode;					
		}
		default:
			break;
	}
	DSL_ERROR("Unsupported type encountered in ADTCreateAndCopy\n");	
	return ps->empty_token();	
}


bool ADTEqual(const ASTNode* a, const ASTNode* b) {
	if (a->type != b->type) {
		return false;	
	}
	if (a->type == ARRAY_TYPE) {		
		if (a->val.a_val.a_type != b->val.a_val.a_type) {
			return false;
		}
		if (a->val.a_val.a_type == ADT_TYPE) {
			if (*(a->val.a_val.a_adt_name) != *(b->val.a_val.a_adt_name)) {
				return false;
			}				
		}
		if (a->val.a_val.a_vector->size() != b->val.a_val.a_vector->size()) {
			return false;	
		}
		for (u_int i = 0; i < a->val.a_val.a_vector->size(); i++) {
			if (ADTEqual((*(a->val.a_val.a_vector))[i], 
					(*(b->val.a_val.a_vector))[i]) == false) {
				return false;
			}
		}
		return true;		
	} else if (a->type == VAR_ADT_TYPE) {
		if (*(a->val.adt_val.adt_type_name) != 
				*(b->val.adt_val.adt_type_name)) {
			return false;
		}
		if (a->val.adt_val.adt_map->size() != b->val.adt_val.adt_map->size()) {
			return false;	
		}
		map<string, ASTNode*>::iterator it = a->val.adt_val.adt_map->begin();
		for (; it != a->val.adt_val.adt_map->end(); it++) {
			map<string, ASTNode*>::const_iterator findIt =
				b->val.adt_val.adt_map->find(it->first);
			if (findIt == b->val.adt_val.adt_map->end()) {
				return false;		
			}
			if (ADTEqual(it->second, findIt->second) == false) {
				return false;	
			}
		}
		return true;
	} else if (a->type == INT_TYPE) {
		if (a->val.i_val != b->val.i_val) {
			return false;	
		}
		return true;
	} else if (a->type == DOUBLE_TYPE) {
		if (a->val.d_val != b->val.d_val) {
			return false;	
		}
		return true;			
	} else if (a->type == STRING_TYPE) {
		if (*(a->val.s_val) != *(b->val.s_val)) {
			return false;	
		}
		return true;		
	}
	DSL_ERROR("Unsupported type for ADTEqual\n");
	return false;
}


ASTNode* variable_create(ParserState* cur_parser, const ASTType in_type, 
		const string* adt_name, const ASTType array_type, int array_size,
		const string* in_string, bool overwrite) {
	ASTNode* retVar 
		= ASTCreate(cur_parser, in_type, adt_name, array_type, array_size);
	if (retVar->type == EMPTY_TYPE) {
		return cur_parser->empty_token();
	}
	if (overwrite) {
		cur_parser->get_var_table()->local_remove(*(in_string));
	}
	if (cur_parser->get_var_table()->insert(*(in_string), retVar) == -1) {
		DSL_ERROR("Variable name collision 2\n");
		return cur_parser->empty_token();
	}
	return retVar;
}

int updateBasicType(ASTNode* a, const ASTNode* b) {
	if (a->type != b->type) {
		DSL_ERROR(
			"UpdateBasicType: Assigning incompatible types %d from %d\n", 
			a->type, b->type);
		return -1;
	}
	switch(a->type) {
		case INT_TYPE:
			a->val.i_val = b->val.i_val;
			break;
		case DOUBLE_TYPE:
			a->val.d_val = b->val.d_val;
			break;
		case STRING_TYPE:
			*(a->val.s_val) = *(b->val.s_val);
			break;
		default:
			DSL_ERROR("Not basic type\n");
			return -1;
	}
	return 0;
}

ASTNode* variable_assign(ParserState* cur_parser, 
		const string* in_string, const ASTNode* in_var) {		
	if (cur_parser->get_var_table()->update(*(in_string), in_var) == -1) {
		DSL_ERROR("Cannot update unknown variable %s found\n", 
			in_string->c_str());
		return cur_parser->empty_token();
	}
	ASTNode* retVar = NULL; 
	if (cur_parser->get_var_table()->lookup(*(in_string), &retVar) == -1) {
		DSL_ERROR("Variable name %s not found\n", in_string->c_str());
		return cur_parser->empty_token();
	}
	return retVar;
}

//	NOTE: This is very inefficient, need better implementation later
int param_list_assign(ParserState* cur_parser, const ASTNode* formal, 
		const vector<ASTNode*>* actual_param) {
	if (formal->type == EMPTY_TYPE) {		
		return 0;	// Void type
	}
	vector<ASTNode*>* formal_param = formal->val.p_val.p_vector;	
	if (formal_param->size() != actual_param->size()) {
		DSL_ERROR("Formal and actual parameters don't match\n");
		return -1;
	}	
	for (u_int i = 0; i < formal_param->size(); i++) {
		if ((*formal_param)[i]->type != NEW_VAR_TYPE) {
			return -1;
		}
		// (*formal_param)[i]->val.v_val.v_array_size should always be 0		
		if (variable_create(cur_parser, 
				(*formal_param)[i]->val.v_val.v_type, 
				(*formal_param)[i]->val.v_val.v_adt_name,
				(*formal_param)[i]->val.v_val.v_array_type,
				//(*formal_param)[i]->val.v_val.v_array_size,
				0,				
				(*formal_param)[i]->val.v_val.v_name,
				false)->type == EMPTY_TYPE) {
			return -1;	
		}
		if (variable_assign(cur_parser, 
				(*formal_param)[i]->val.v_val.v_name,
				(*actual_param)[i])->type == EMPTY_TYPE) {
			return -1;		
		}
	}	
	return 0;
}		

ASTNode* mk_empty(ParserState* in_state) {
	ASTNode* thisNode = in_state->get_var_table()->new_stack_ast();
	if (thisNode == NULL) {
		return in_state->empty_token();	
	}
	thisNode->type = EMPTY_TYPE;
	return thisNode; //	Don't bother init the ASTVal
}

ASTNode* mk_adt(ParserState* in_state, string* adt_name, ASTNode* param_list) {
	ASTNode* thisNode = in_state->get_var_table()->new_stack_ast();
	if (thisNode == NULL) {
		return in_state->empty_token();	
	}	
	thisNode->type = DEF_ADT_TYPE;
	thisNode->val.adt_val.adt_type_name = adt_name;
	thisNode->val.adt_val.adt_param = param_list;