/********************************************************************************
*
* The C++ code generator for converting the intermediate code into C++.
* The generated code contains calls to the evaluator functions (evaluator/eval.h)
*
* Copyright (c) 1999-2003 by Leonidas Fegaras, the University of Texas at
*     Arlington. All rights reserved.
* Programmer: Leonidas Fegaras, UTA
* Date: 8/17/99
*
*********************************************************************************/

#include "odl.h"
#include "typecheck.h"
#include "constant.h"

extern char* ffile;
extern char* mfile;

extern ofstream fout;
extern ofstream mout;

extern int parser_line;


/* if set to true, it prints the evaluation code in *.tmp.h */
static bool print_evaluation_code = false;


/* flag to indicate whether we are compiling or interpreting queries */
extern bool interpreterp;


bool persistent_constructions = false;


/* global environment for group-by vars */
extern GEnv gvars;
extern Schema gbinds;


/* set it to false if you don't want query unnesting */
extern bool query_unnesting;


/* set it to false if you don't want pointer joins (ie. no materialization of path expressions)	*/
extern bool pointer_joins;


/* set it to false if you don't want convertion of unnests to pointer joins)    */
extern bool unnests_to_joins;

extern char* username;

static bool in_function = false;

int size_in_bytes ( Expr tp, bool is_raw_data = false );


/* the size of the stack frame (_scope) that holds the local vars */
static list<int>* scope_stack = new list<int>;

static int current_scope_size = 0;

void new_variable_scope () {
  scope_stack = Cons(0,scope_stack);
};

int close_variable_scope () {
  int n = scope_stack->hd;
  scope_stack = scope_stack->tl;
  return n;
};

int new_scope_variable () {
  return scope_stack->hd++;
};

int scope_variable_number () {
  return scope_stack->hd;
};

/* the local environment that binds local variables to frame offsets in _scope */
static Schema local_variables = new binding<Expr>;


/* return the variables in e that are not bound by some lambda binding or iterator
 * -- defined in optimizer.gen					*/
list<Expr>* free_variables ( Expr e, list<Expr>* except );


static list<String>* collection_equalities = new list<String>;

bool member ( string s, list<String>* ls ) {
  for(list<String>* r = ls; r->consp(); r=r->tl)
     if (s.eq(r->hd))
	return true;
  return false;
};


/* return the variables of a pattern */
list<Expr>* pattern_variables ( Expr pattern );


/* returns the physical plan with the smallest cost -- defined in rule_based_opt.gen */
Expr best_evaluation_order ( Expr e );


/* generate an equality test between x and y (of type tp) -- defined in code_generator.gen */
Expr generate_equality ( Expr tp1, Expr tp2, Expr x, Expr y );

/* does e generate a collection? -- defined in code_generator.gen */
bool bulk_operation ( Expr e );


/* create a sort key -- defined in code_generator.gen */
Expr translate_key ( Expr relation, list<Expr>* attributes, Schema sch, Schema stuple, int len );


String current_module_name = new string("School");


static bool use_global_tuple = false;


void new_active_stream ();
Expr close_active_stream ( Expr return_value );


static pair<char*,int>* generated_names[100];

/* a mapping from names to counters to generate new names eg. _get56 */
String new_name ( const char* s ) {
  short i = 0;
  for(; i<100 && generated_names[i]; i++)
     if (strcmp(generated_names[i]->first,s) == 0)
     {  int k = generated_names[i]->second;
	generated_names[i]->second++;
	return new string(fform("_%s%i",generated_names[i]->first,generated_names[i]->second));
     };
  if (i >= 100)
     odmg_error("run out of variable names");
  generated_names[i] = new pair<char*,int>((char*) s,0);
  return new string(fform("_%s0",s));
};


/* all generated C++ typedefs are memoized to save compilation time */
binding<Expr>* defined_typedefs = new binding<Expr>;


/* if typedef e is memoized, return the name of the typedef */
String defined_typedef ( Expr e ) {
  for(list<String>* ns = defined_typedefs->names(); ns->consp(); ns=ns->tl)
     if (defined_typedefs->find(ns->hd)->eq(e))
	return ns->hd;
  return NULL;
};


/* memoize typedef e under the name, name */
void store_typedef ( String name, Expr e ) {
  defined_typedefs = defined_typedefs->extend(name,e);
};


void store_struct_name ( const char* type, const char* name ) {
  String nm = new string(name);
  if (!defined_typedefs->in(nm))
     store_typedef(nm,string_to_expr(new string(type)));
};


int count_local_assignments ( Expr e ) {
  #case e
  | assign(...r,`u)
	=> { int res = 0;
	     for(; r->consp(); r=r->tl)
		#case r->hd
		|  bind(_,`e,_)
			=> res = 1 + res + count_local_assignments(e);
		|  static_bind(_,`e,_,_)
			=> res = 1 + res + count_local_assignments(e);
		#end;
	     return res + count_local_assignments(u);
	   };
  | `f(...r)
	=> { int res = 0;
	     for(; r->consp(); r=r->tl)
		res = res + count_local_assignments(r->hd);
	     return res;
	   };
  | _ => return 0;
  #end;
};


/* ... defined later */
string translate_type ( Expr e, bool pointerp, ofstream &fout, bool struct_equalities );
string generate_code ( Expr e, bool pointerp );


/* translate a scoped collection variable */
string translate_collection_variable ( Expr e, Expr counter, Expr tp, string prefix ) {
  String name = new_name("collection");
  bool ugt = false;
  #case e
  | `f[tuple_reference(x,...r)] => ugt = true;
  #end;
  use_global_tuple = ugt;
  string s = generate_code(e,true);
  string tes = translate_type(tp,false,fout,true);
  string cs = generate_code(counter,false);
  fout << "\nstatic tuple " << name << " () {\n"
       << "  static " << tes << " _v;\n"
       << "  if (" << cs << " == 0) _v = *(" << tes << "*) " << s << ";\n"
       << "  if (" << cs << " < _v.cardinality())\n";
  string sp = (prefix.eq(new string(""))) ? string("") : ("(" + prefix + ")->concat");
  #case tp
  | `f(`et)
	: et->variablep() && classp(et->name())
	=> fout << "     return " << sp << "(new Tuple((sm_ref*) _v[" << cs << "++]));\n";
  | `f(`et)
	=> { string ts = translate_type(et,false,fout,true);
	     fout << "  {  " << ts << "* _res = new (GC) " << ts << "(_v[" << cs << "++]);\n"
		  << "     return " << sp << "(new Tuple((void*) _res));\n  }\n"; 
	   };
  #end;
  fout << "  else { " << cs << " = 0; return invalid_data(); };\n};\n";
  use_global_tuple = false;
  if (ugt)
     return "(global_tuple=x, &" + *name + ")";
  else return "&" + *name;
};


string translate_raw_type ( Expr tp, ofstream &fstr ) {
  #case tp
  | string => return "raw_string";
  | scope(`etp)
	=> return translate_raw_type(etp,fstr);
  | `f(`tp)
	: collectionp(f)
	=> return "raw_sequence";
  | `v  : v->variablep() && classp(v->name())
	=> return "raw_ref";
  | _ => return translate_type(tp,false,fstr,false);
  #end;
};


static list<Expr>* all_created_objects = Nil;

bool is_created_object ( Expr e ) {
  #case e
  | project(`x,...r)
      => return is_created_object(x);
  | union_case(`x,...r)
      => return is_created_object(x);
  | _ : e->variablep()
      => return member(e,all_created_objects);
  | _ => return true;
  #end;
};


/* translate an ODL type into a C++ type. All structs become typedefs
   because C++ doesn't allow struct types in function heads */
string translate_type ( Expr e, bool pointerp, ofstream &fstr, bool struct_equalities ) {
  string s = "";
  #case e
  | scope(`nm)
	=> return translate_type(nm,pointerp,fstr,struct_equalities);
  | struct(...r)
	=> { String name = defined_typedef(e);
	     if (name != NULL)
		 return *name + (pointerp ? "*" : "");
	     name = new_name("S");
	     store_typedef(name,e);
	     string s = "\ntypedef struct " + *name + " { ";
	     for(; r->consp(); r=r->tl)
		#case r->hd
		| bind(`v,`tp)
		     => s = s+translate_type(tp,false,fstr,struct_equalities)+" "+(*v->name())+"; ";
		#end;
	     fstr << s << " } " << name << ";\n";
	     return *name + (pointerp ? "*" : "");
	   };
  | enum(`nm,...r)
	=> return *nm->name();
  | union(`nm,`ttp,...cases)
	=> { list<Expr>* ns = Nil;
	     for (list<Expr>* r=cases; r->consp(); r=r->tl)
		 #case r->hd
		 | case(`etp,`nm,...s)
			=> ns = Cons(#<bind(`nm,`etp)>,ns);
		 #end;
	     ns = ns->reverse();
	     return translate_type(#<struct(bind(tag,`ttp),bind(value,struct(...ns)))>,pointerp,fstr,struct_equalities);
	   };
  | `f(`tp)
	: collectionp(f)
	=> { string stp = translate_type(tp,false,fstr,struct_equalities);
	     return "Sequence<" + stp + (pointerp ? " >*" : " >");
	   };
  | `f(`tp)
	: collectionp(f)
	=> return (pointerp ? "sm_sequence*" : "sm_sequence");
  | string => return (pointerp ? "sm_string*" : "sm_string");
  | integer => return (pointerp ? "long*" : "long");
  | int => return (pointerp ? "int*" : "int");
  | unsigned_long => return (pointerp ? "unsigned long*" : "unsigned long");
  | unsigned_short => return (pointerp ? "unsigned short*" : "unsigned short");
  | real => return (pointerp ? "float*" : "float");
  | boolean => return (pointerp ? "bool*" : "bool");
  | bool => return (pointerp ? "bool*" : "bool");
  | key => return (pointerp ? "Key*" : "Key");
  | tuple => return (pointerp ? "tuple" : "???");
  | stream => return (pointerp ? "Stream*" : "Stream");
  | any => return (pointerp ? "sm_ref*" : "sm_ref");
  | `v  : v->variablep()
	=> if (classp(v->name()))
	      return s+"Ref<" + (*v->name()) + (pointerp ? ">*" : ">");
	   else {  Expr tp = get_scoped_type(v);
		   if (tp->eq(#<none>) || tp->eq(v))
		      return *v->name() + (pointerp ? "*" : "");
		   else return translate_type(tp,pointerp,fstr,struct_equalities);
		};
  | `f(...r)
	=> { string s = translate_type(f,false,fstr,struct_equalities) + "(";
	     for(; r->consp(); r=r->tl)
		s = s + translate_type(r->hd,false,fstr,struct_equalities) + ((r->tl->consp()) ? "," : "");
	     return s + (pointerp ? ")*" : ")");
	   };
  #end;
};


string tag_name ( Expr e ) {
  #case e
  | scope(`nm) => return *nm->name();
  | _ : e->variablep() => return *e->name();
  | _ => return string("error");
  #end;
};


string generate_code ( Expr e, bool pointerp ) {
  #case e
  | value(`x,`tp)
	=> return generate_code(x,pointerp);
  | value(`x,`tp)
	=> return (pointerp ? "((" : "*((") + translate_type(tp,false,fout,true) + "*) ("
		  + generate_code(x,false) + ").value)";
  | stream(`e)
	: e->variablep() && local_variables->in(e->name())
	=> return fform(pointerp ? "((Stream*) _scope[%i])" : "((Stream*) _scope[%i])*",
		       local_variables->find(e->name())->arguments()->hd->info.Integer);
  | stream(`v)
	=> if (pointerp)
	      return *v->name();
	   else return "*" + *v->name();
  | new_tuple_reference(`x)
	=> if (pointerp)
	      return "new Tuple((sm_ref*) " + generate_code(x,true) + ")";
	   else return "Tuple((sm_ref*) " + generate_code(x,true) + ")";
  | new_tuple_value(`x)
	=> if (pointerp)
	      return "new Tuple((void*) (" + generate_code(x,true) + "))";
	   else return "Tuple((void*) (" + generate_code(x,true) + "))";
  | call(referencep,_,`x,`n)
	=> return (pointerp ? "new (GC) bool((" : "((")
		  + generate_code(x,false) + ")[" + generate_code(n,false) + "].referencep())";
  | call(valuep,_,`x,`n)
	=> return (pointerp ? "new (GC) bool((" : "((")
		  + generate_code(x,false) + ")[" + generate_code(n,false) + "].valuep())";
  | call(import_string,_,`x)
	=> return (pointerp ? "(sm_string*)import_string(&" : "*(sm_string*)import_string(&")
		  + generate_code(x,false) + ")";
  | call(import_ref,_,`x)
	=> return (pointerp ? "(sm_ref*)import_ref(&" : "*(sm_ref*)import_ref(&")
		  + generate_code(x,false) + ")";
  | call(import_sequence,_,`x,`n,`f)
	=> return (pointerp ? "(sm_sequence*)import_sequence(&" : "*(sm_sequence*)import_sequence(&")
		  + generate_code(x,false) + "," + generate_code(n,true) + "," + generate_code(f,true) + ")";
  | tuple_value(`x,`n,`tp)
	=> if (pointerp)
	      return "((" + translate_type(tp,true,fout,true) + ")(" + generate_code(x,false)
		     + ")[" + string(fform("%i",n->info.Integer)) + "].value())";
	   else return "(*(" + translate_type(tp,true,fout,true) + ")(" + generate_code(x,false)
		       + ")[" + string(fform("%i",n->info.Integer)) + "].value())";
  | tuple_reference(`x,`n,`tp)
	=> if (pointerp)
	      return "((" + translate_type(tp,true,fout,true) + ")(" + generate_code(x,false)
		     + ")[" + string(fform("%i",n->info.Integer)) + "].reference())";
	   else return "(*(" + translate_type(tp,true,fout,true) + ")(" + generate_code(x,false)
		       + ")[" + string(fform("%i",n->info.Integer)) + "].reference())";
  | eq_oid(`x,`y)
	=> { string tx = generate_code(x,false);
	     string ty = generate_code(y,false);
	     return (pointerp ? "new (GC) bool((" : "((") + tx + ").oid() == (" + ty + ").oid())";
	   };
  | empty_collection(`tp,`n)
	=> return (pointerp ? "(new (GC) Sequence< " : "*(new (GC) Sequence< ") + translate_type(tp,false,fout,true) + " >)";
  | if(`c,`x,`y)
	=> return "((" + generate_code(c,false) + ") ? ("
		  + generate_code(x,pointerp) + ") : (" + generate_code(y,pointerp) + "))";
  | internal_call(`f,`loc,`tp,...r)
	=> { string res = pointerp ? ("new (GC) " + translate_type(tp,false,fout,true) + "(") : string("(");
	     if (f->name()->length() < 3)
		if (r->length() == 1)
		   return res + *f->name() + "(" + generate_code(r->hd,false) + "))";
		else return res + "(" + generate_code(r->hd,false) + ") "
			    + *f->name() + " (" + generate_code(r->tl->hd,false) + "))";
	     res = res + *f->name() + "(";
	     for(; r->consp(); r=r->tl)	
	     {  res = res + generate_code(r->hd,false);
		if (r->tl->consp())
		   res = res + ",";
	     };
	     return res + "))";
	   };
  | function_call(`f,`tp,...r)
	=> { string res = fform("(_new_scope(%i), _return_from_scope(%i,",current_scope_size,current_scope_size);
	     res = res + (pointerp ? "(" : "*(") + *f->name() + "(";
	     for(; r->consp(); r=r->tl)	
	     {  res = res + generate_code(r->hd,true);
		if (r->tl->consp())
		   res = res + ",";
	     };
	     return res + "))))";
	   };
  | call(aggregate,_,`s,`z,`acc)
	=> { Expr tp = #<none>;
	     #case acc
	     | lambda(`rtp,...r) => tp = rtp;
	     #end;
	     return (pointerp ? "((" : "(*(")
			+ translate_type(tp,true,fout,true) + ")aggregate((Stream*)"
			+ generate_code(s,true) + "," + generate_code(z,true) + ",(void*(*)(void*,void*))"
			+ generate_code(acc,true) + "))";
	   };
  | call(reduce_list,_,`acc,`z,`x)
	=> { Expr tp = #<none>;
	     #case acc
	     | lambda(`rtp,...r) => tp = rtp;
	     #end;
	     return (pointerp ? "((" : "(*(")
			+ translate_type(tp,true,fout,true) + ")reduce_list((void*(*)(void*,void*))" + generate_code(acc,true)
			+ "," + generate_code(z,true) + "," + generate_code(x,true) + "))";
	   };
  | call(`f,`loc,...r)
	=> { if (f->name()->length() < 3)
		if (r->length() == 1)
		   return *f->name() + "(" + generate_code(r->hd,false) + "))";
		else return "(" + generate_code(r->hd,false) + ") "
			    + *f->name() + " (" + generate_code(r->tl->hd,false) + "))";
	     string res = (pointerp ? "" : "*") + *f->name() + "(";
	     for(; r->consp(); r=r->tl)
	     {  /* last arg of some functions must be coerced */
		if ((f->eq(#<collect_values>) || f->eq(#<collect_references>) || f->eq(#<list_equality>) || f->eq(#<set_merge>)
			 || f->eq(#<bag_equality>) || f->eq(#<set_equality>)) && r->tl->nullp())
		   res = res + "(bool*(*)(const char*,const char*))";
		res = res + generate_code(r->hd,true);
		if (r->tl->consp())
		   res = res + ",";
	     };
	     return res + ")";
	   };
  | lambda(`out_tp,...args,`body)
	=> { String name = new_name("F");
	     string s = "\nstatic " + translate_type(out_tp,true,fout,true) + " " + *name + " (";
	     for(list<Expr>* r = args; r->consp(); r=r->tl)
	     {  #case r->hd
		| bind(`v,`tp)
		     => s = s + translate_type(tp,true,fout,true) + " " + *v->name();
		#end;
	        if (r->tl->consp())
		   s = s + ", ";
	     };
	     string bcode = generate_code(body,true);
	     fout << s << ") {\n  return " << bcode << ";\n};\n";
	     return "&" + *name;
	   };
  | project(`x,`a,_,`rtp,`tp,...r)
	: tp->variablep() && classp(tp->name())
	=> #case rtp
      | `f(`etp) : (collectionp(f) && is_created_object(x))
		=> if (pointerp)
		      return "(new (GC) " + translate_type(rtp,false,fout,true)
			     + "((Sequence<" + translate_raw_type(etp,fout) + " >)(((Ref<" + *tp->name()
			     + ">) " + generate_code(x,false) + ")->" + *a->name() + ")))";
		   else return "(" + translate_type(rtp,false,fout,true)
			       + "((Sequence<" + translate_raw_type(etp,fout) + " >)(((Ref<" + *tp->name() + ">) "
			       + generate_code(x,false) + ")->" + *a->name() + ")))";
	   | string => if (pointerp)
		     return "(new (GC) sm_string(((Ref<" + *tp->name()
			    + ">) " + generate_code(x,false) + ")->" + *a->name() + "))";
		  else return "(((Ref<" + *tp->name() + ">) "
			      + generate_code(x,false) + ")->" + *a->name() + ")";
	   | _ => if (pointerp)
		     return "(&(((Ref<" + *tp->name()
			    + ">) " + generate_code(x,false) + ")->" + *a->name() + "))";
		  else return "(((Ref<" + *tp->name() + ">) "
			      + generate_code(x,false) + ")->" + *a->name() + ")";
	   #end;
  | project(`x,`a,_,string,`tp,...r)
	=> if (pointerp)
	      return  "(new (GC) sm_string(("
		      + generate_code(x,false) + ")." + *a->name() + "))";
	   else return "((" + generate_code(x,false) + ")." + *a->name() + ")";

  | project(`x,`a,_,`rtp,`tp,...r)
	=> #case rtp
	   | `f(`etp) : (collectionp(f) && is_created_object(x))
		=> if (pointerp)
		      return "(new (GC) " + translate_type(rtp,false,fout,true)
			     + "((Sequence<" + translate_raw_type(etp,fout) + " >)(" + generate_code(x,false) + ")." + *a->name() + "))";
		   else return "(" + translate_type(rtp,false,fout,true)
			       + "((Sequence<" + translate_raw_type(etp,fout) + " >)(" + generate_code(x,false) + ")." + *a->name() + "))";
	   | string => if (pointerp)
		     return "(new (GC) sm_string((" + generate_code(x,false) + ")." + *a->name() + "))";
		  else return "((" + generate_code(x,false) + ")." + *a->name() + ")";
	   | _ => if (pointerp)
		     return  "(&((" + generate_code(x,false) + ")." + *a->name() + "))";
		  else return "((" + generate_code(x,false) + ")." + *a->name() + ")";
	   #end;
  | project(...r)
	=> odmg_error("Illegal projection",e);
  | make_struct(`tp)
	=> return "new " + translate_type(tp,false,fout,true);
  | make_union(`tp,`tag)
	=> {  string stp = translate_type(tp,false,fout,true);
	      String nm = new_name("X");
	      return "({ " + stp + "* " + *nm + " = new " + stp + "; " + *nm + "->tag = " + *tag->name() + "; " + *nm + "; })";
	   };
  | set_union_tag(`d,`tag)
	=> return "(" + generate_code(d,false) + ").tag = " + generate_code(tag,false);
  | message(scope(`tp),`out_type,`x,`method,...r)
	=> return generate_code(#<message(`tp,`out_type,`x,`method,...r)>,pointerp);
  | message(`tp,`out_type,`x,`method,...r)
	=> { string res = *tp->name() + "__." + *method->name() + "((Ref<" + *tp->name() + ">) "
			  + generate_code(x,false);
	     for(; r->consp(); r=r->tl)	
		res = res + "," + generate_code(r->hd,false);
	     return (pointerp ? ("(new (GC) "+translate_type(out_type,false,fout,true)+"(") : string("((")) + res + ")))";
	   };
  | scoped_variables(`n,`tp)
      : n->integerp()
      => return (pointerp ? "((" : "*((") + translate_type(tp,true,fout,true)
		+ ((in_function) ? fform(") _scoped_variables[current_scoped_variable_number-%i])",n->info.Integer)
				 : fform(") _scoped_variables[%i])",n->info.Integer));
  | translate_collection_variable(`v,`counter,`tp,`prefix)
      => return translate_collection_variable(v,counter,tp,prefix->eq(#<NULL>) ? string("") : generate_code(prefix,true));
  | union_tag(`x)
	=> return (pointerp ? "new (GC) long((" : "((") + generate_code(x,false) + ").tag)";
  | union_case(`x,`nm,`tp,_)
	=> return (pointerp ? ( "new (GC) " + translate_type(tp,false,fout,true) + "((") : string("(("))
		  + generate_code(x,false) + ").value." + *nm->name() + ")";
  | update(project(`x,`a,`n,`tp,`rtp,...r),`s,_)
	=> #case get_scoped_type(tp)
	   | `f(`etp)
		: (collectionp(f) && rtp->variablep() && classp(rtp->name()))
		=> {  string dtp = "Sequence<" + translate_raw_type(etp,fout) + " >";
		      string stp = translate_type(#<`f(`etp)>,true,fout,true);
		      return "(" + dtp + ")(((Ref<" + *rtp->name() + ">) "
			      + generate_code(x,false) + ")->" + *a->name() + ") = *("
			      + stp + ")" + generate_code(s,true);
		   };
	   | `f(`etp)
	       : collectionp(f) && is_created_object(x)
		=> {  string dtp = "Sequence<" + translate_raw_type(etp,fout) + " >";
		      string stp = translate_type(#<`f(`etp)>,true,fout,true);
		      return "((" + dtp + ")(" + generate_code(x,false) + ")." + *a->name() + ") = *("
			      + stp + ")" + generate_code(s,true);
		      return "(" + generate_code(x,false) + ")." + *a->name() + " = *("
			      + stp + ")" + generate_code(s,true);
		   };
	   | `f(`etp)
		: collectionp(f)
		=> {  string stp = translate_type(#<`f(`etp)>,true,fout,true);
		      return "(" + generate_code(x,false) + ")." + *a->name() + " = *("
			      + stp + ")" + generate_code(s,true);
		      return "(" + generate_code(x,false) + ")." + *a->name() + " = *("
			      + stp + ")" + generate_code(s,true);
		   };
	   | _ => return generate_code(#<project(`x,`a,`n,`tp,`rtp,...r)>,false) + " = *(" + generate_code(s,true) + ")";
	   #end;
  | update(`d,`s,_)
	=> return generate_code(d,false) + " = " + generate_code(s,false);
  | sequence_insert(project(`x,`a,`n,`f(`etp),`tp,...r),`e)
	=> {  string rtp = translate_raw_type(etp,fout);
	      string stp = translate_type(tp,false,fout,true);
	      string dest = generate_code(x,false);
	      String nm = new_name("X");
	      string s = "{ " + rtp + " " + *nm + " = (" + rtp + ")(*" + generate_code(e,true) + "); ";
	      if (tp->variablep() && classp(tp->name()))
	         return s + "((Sequence<" + rtp + " >)((" + dest + ")->" + *a->name() + ")).insert(" + *nm + "); }";
	      else return s + "((Sequence<" + rtp + " >)((" + dest + ")." + *a->name() + ")).insert(" + *nm + "); }";
	   };
  | sequence_remove(project(`x,`a,`n,`f(`etp),`tp,...r),`e)
	=> {  string rtp = translate_raw_type(etp,fout);
	      string stp = translate_type(tp,false,fout,true);
	      string dest = generate_code(x,false);
	      String nm = new_name("X");
	      string s = "{ " + rtp + " " + *nm + " = (" + rtp + ")(*" + generate_code(e,true) + "); ";
	      if (tp->variablep() && classp(tp->name()))
	         return s + "((Sequence<" + rtp + " >)((" + dest + ")->" + *a->name() + ")).remove(" + *nm + "); }";
	      else return s + "((Sequence<" + rtp + " >)((" + dest + ")." + *a->name() + ")).remove(" + *nm + "); }";
	   };
  | assign(...binds,`val)
	=> { string res = "  (";
	     for(list<Expr>* r = binds; r->consp(); r=r->tl)
		#case r->hd
		|  bind(`v,`e,`tp)
			=> {  int loc = new_scope_variable();
			      local_variables = local_variables->extend(v->name(),#<bind(`(integer(loc)),`tp)>);
			      res = res + fform("_scope[%i] = (void*) ",loc) + generate_code(e,true) + ",\n   ";
			   };
		|  static_bind(`v,`e,`test,`tp)
			=> {  int loc = new_scope_variable();
			      local_variables = local_variables->extend(v->name(),#<bind(`(integer(loc)),`tp)>);
			      res = res + fform("_scope[%i] = (void*) ((",loc)
					+ generate_code(test,false)
					+ ") ? "
					+ generate_code(e,true)
					+ fform(" : _scope[%i]),\n   ",loc);
			   };
		#end;
	     return res + generate_code(val,pointerp) + ")";
	   };
  | assign(...binds,`val)	/* use global vars instead of a stack frame (so no recursion) */
	=> { string res = "  (";
	     for(list<Expr>* r = binds; r->consp(); r=r->tl)
		#case r->hd
		|  bind(`v,`e,`tp)
			=> { string ts = translate_type(tp,true,fout,true);
			     fout << "\nstatic " << ts << " " << v << ";\n";
	     		     res = res + *v->name() + " = (" + ts + ") " + generate_code(e,true) + ",\n   ";
			   };
		#end;
	     return res + generate_code(val,pointerp) + ")";
	   };
  | insert(`value,`set)
	=> return "(" + generate_code(set,true) + ")->append(" + generate_code(value,false) + ")";
  | map(`x,`tp,`f,`set)
	=> {  string ns = generate_code(set,true);
	      string nf = generate_code(f,true);
	      string ts = translate_type(tp,true,fout,true);
	      return "for(int i=0; i<" + ns + "->cardinality(); i++) "
		     + "({ " + ts + " " + *x->name() + " = (" + ts + ") " + ns + "->access(i); " + nf + "; })";
	   };
  | define(`v,`u,`tp)
	=> {  string stp = translate_type(tp,true,fout,true);
	      #case u
	      | call(new_transient_object,...r)
	           => all_created_objects = Cons(v,all_created_objects);
	      | call(new_persistent_object,...r)
	           => all_created_objects = Cons(v,all_created_objects);
	      #end;
	      return stp + " " + generate_code(v,true) + " = (" + stp + ") " + generate_code(u,true);
	   };
  | block(...r,`v)
	=> {  string res = (pointerp) ? "({ " : "*({ ";
	      for(; r->consp(); r=r->tl)
		 res = res + generate_code(r->hd,true) + ";\n ";
	      return res + generate_code(v,true) + "; })";
	   };
  | true => return (pointerp ? "new (GC) bool(true)" : "true");
  | false => return (pointerp ? "new (GC) bool(false)" : "false");
  | NULL => return "NULL";
  | nil => return "NULL";
  | x : use_global_tuple
      => return pointerp ? "global_tuple" : "*global_tuple";
  | _ : e->variablep() && local_variables->in(e->name())
      => {  string tp = translate_type(local_variables->find(e->name())->arguments()->tl->hd,true,fout,true);
	    if (pointerp)
	       return fform("((%s) _scope[%i])",
			   tp.content(),
			   local_variables->find(e->name())->arguments()->hd->info.Integer);
	    else return fform("*((%s) _scope[%i])",
			     tp.content(),
			     local_variables->find(e->name())->arguments()->hd->info.Integer);
	 };
  | _ : e->variablep()
      => return (pointerp ? "" : "*") + *e->name();
  | _ => if (e->integerp())
	    return (pointerp ? ("new (GC) long(" + string(fform("%i",e->info.Integer)) + ")")
			       : string(fform("%i",e->info.Integer)));
	 else if (e->stringp())
	    return (pointerp ? ("new (GC) sm_string(\"" + *e->info.Estring + "\")")
			       : ("sm_string(\"" + *e->info.Estring + "\")"));
	 else if (e->realp())
	    return (pointerp ? ("new (GC) float(" + string(fform("%f",e->info.Real)) + ")")
			       : string(fform("%f",e->info.Real)));
	 else odmg_error("Don't know how to translate it to C++",e);
  #end;
};


Expr translate_stream_opr ( Expr e, Schema &sch, Schema &stuple, bool materializep = false, bool streamp = true );
Expr translate_expr ( Expr e, Schema sch, Schema stuple, int size );


/* translates OQL intermediate code into C++ code */
Schema generate_opr ( Expr e, String &name, String &init, bool pointerp, bool streamp = true ) {
  Schema sch = new binding<Expr>;
  Schema stuple = new binding<Expr>;
  new_active_stream();
  Expr ne = close_active_stream(translate_stream_opr(e,sch,stuple,false,streamp));
  current_scope_size = count_local_assignments(ne);
  string sinit = "";
  init = new_name("init");
  #case ne
  | stream(_)
	 : streamp
	 => name = new string(generate_code(ne,pointerp));
  | assign(...binds,`s)
	=> { sinit = generate_code(#<assign(...binds,NULL)>,false) + ";\n";
	     name = new string(generate_code(s,pointerp));
	   };
  | _ : streamp
	=> { name = new_name();
	     sinit = *name + " = new Stream("
		     + translate_collection_variable(ne,#<i>,type_of(e,sch),string("")) + ");\n";
	    };
  | _ => name = new string(generate_code(ne,pointerp));
  #end;
  fout << "\nstatic void " << init << " () {\n" << sinit << "};\n";
  return sch;
};


/* translate an OQL non bulk operation */
string generate_expr ( Expr e, Schema &sch ) {
  return generate_code(translate_expr(e,sch,sch,sch->length()),true);
};


Expr translate ( Expr e );
Expr translate_query ( Expr e, Schema &sch, Schema &stuple, bool streamp = true );
Expr optimize_query ( Expr query );


bool updatep ( Expr e ) {
  #case e
  | `f(...r)
	: f->eq(#<update>) || f->eq(#<insert>) || f->eq(#<delete>)
	=> return true;
  | _ => return false;
  #end;
};


String process_query ( Expr e, Expr &tp, bool streamp, String &init, bool pointerp, Expr &pq ) {
  fout << "\n/********************************************************************************\n";
  fout << "\nFound in Line: " << parser_line << endl;
  fout << "\nQuery:\n";
  e->pretty_print(0,fout);
  Expr u = translate(e);
  Schema vars = new binding<Expr>;
  tp = type_of(u,vars,true);
  fout << "\n\nComprehension Calculus Form:\n";
  u->pretty_print(0,fout);
  fout << endl;
  fout << "\nType of the Query: " << tp;
  Expr oq = optimize_query(u);
  fout << "\n\nOptimized Algebraic Form:\n";
  oq->pretty_print(0,fout);
  pq = best_evaluation_order(oq);
  fout << "\n\nPhysical Plan:\n";
  pq->pretty_print(0,fout);
  type_of(pq,new binding<Expr>);
  Schema sch = new binding<Expr>;
  Schema stuple = new binding<Expr>;
  gvars = new list<pair<Expr,Expr>*>;
  gbinds = new binding<Expr>;
  if (print_evaluation_code)
  {  fout << "\n\nEvaluation Code:\n";
     translate_stream_opr(pq,sch,stuple,false,streamp)->pretty_print(0,fout);
  };
  fout << "\n\n********************************************************************************/\n";
  gvars = new list<pair<Expr,Expr>*>;
  gbinds = new binding<Expr>;
  String name = new_name("F");
  String nx;
  #case tp
  | `f(`et)
	: streamp && collectionp(f)
	=> {  string tname = translate_type(et,false,fout,true);
	      string cp = (f->eq(#<set>)) ? "true" : "false";
	      generate_opr(pq,nx,init,pointerp,true);
	      fout << "\nstatic const bool " << name << " ( " << tname << " &_res ) {\n"
		   << "  return access(" << nx << ",_res," << cp << ");\n};\n";
	   };
  | `f(`et)
	: collectionp(f) && !updatep(e)
	=> {  string tname = translate_type(tp,false,fout,true);
	      generate_opr(pq,nx,init,pointerp,false);
	      #case et
	      | scope(`etp) => et = etp;
	      #end;
	      if (!bulk_operation(pq))
		 fout << "\nstatic void " << name << " ( " << tname << " &_res ) {\n"
		      << "  _res = *((" << tname << "*)" << nx << ");\n};\n";
	      else {
	        Expr size = integer(size_in_bytes(et));
	        Expr eq = generate_equality(et,et,#<value(x,`et)>,#<value(y,`et)>);
	        Expr eqf = #<lambda(bool,bind(x,`et),bind(y,`et),`eq)>;
	        string nf = generate_code(eqf,false);
	        String bname = new_name("F");
	        string etname = translate_type(et,false,fout,true);
		fout << "\nstatic void " << name << " ( " << tname << " &_res ) {\n";
		string uniquep = (f->eq(#<set>)) ? "new (GC) bool(true)" : "new (GC) bool(false)";
	        if (et->variablep() && classp(et->name()))
		   fout << "  _res = *(" << tname << "*) collect_references(" << nx << "," << uniquep
			<< ",(bool*(*)(const char*,const char*))" << nf <<");\n};\n";
		else fout << "  _res = *(" << tname << "*) collect_values(" << nx << ",new (GC) long("
			  << size << ")," << uniquep << ",(bool*(*)(const char*,const char*))" << nf <<");\n};\n";
	      };
	   };
  | _ => {  generate_opr(pq,nx,init,pointerp,streamp);
	    return nx;
	 };
  #end;
  return name;
};


bool member ( String s, list<String>* r );
int find_function ( const char* function_name );
int store_function ( const char* function_name, const void* function_address, const short num_of_all_args, const short num_of_functional_args );
Expr preprocess_expr ( Expr e );


void print_scanners ( Expr type ) {
  return;
  #case type
  | struct(...r)
	=> { string tname = translate_type(type,false,mout,false);
	     mout << "store_struct_name(\"";
	     type->write(mout);
	     mout << "\",\"" << tname << "\"); ";
	     for(; r->consp(); r=r->tl)
	        #case r->hd
	        | bind(_,`tp) => print_scanners(tp);
	        #end;
	   };
  | `f(`tp)
	: collectionp(f)
	=> { string s = translate_type(type,false,mout,false);
	     string es = translate_type(tp,false,mout,false);
	     string fname = "accessor_name";
             if (find_function(fname.content()) < 0 )
	     {  store_function(fname.content(),(void*) &print_scanners,2,0);
		mout << "store_function(\"" << fname << "\",(void*) &" << fname << ",2,0);\n";
	        fout << "\ntuple " << fname << " ( " << s << "* s, long* loc ) {\n"
		     << "  if (s->cardinality() <= *loc)\n"
		     << "     return invalid_data();\n"
		     << "  else return new Tuple((void*) new (GC) " << es << "((*s)[*loc]));\n"
		     << "};\n";
	     };
	     print_scanners(tp);
	   };
  #end;
};


void process_oql ( Expr e ) {
  Expr tp, pq;
  String init;
  #case e
  | module(`v)
	=> { set_current_module(v->name());
	     current_module_name = v->name();
	     mout << "#include " << get_declaration_binding(new string(fform("%s::_file_name",current_module_name->content()))) << "\n";
	     mout << "#include \"" << ffile << "\"\n\n";
	   };
  | foreach(`v,`e)
	=> { String s = process_query(e,tp,true,init,true,pq);
	     #case tp
	     | `f(`tp)
		  : collectionp(f)
		  => {  string stp = translate_type(tp,false,fout,true);
			translate_type(#<`f(`tp)>,false,fout,true);
			put_in_current_scope(v->name(),tp);
			mout << "{ " << stp << " " << v << "; _scoped_variables["
			     << last_scoped_var() << "] = (void*) &" << v << "; "
			     << init << "(); while(" << s << "(" << v << ")) ";
		     };
	     | _ => odmg_error("Expected a collection",e);
	     #end;
	   };
  | assign(`x,`e)
	: x->variablep()
	=> { String s = process_query(e,tp,false,init,true,pq);
	     Expr stp = find_scoped_variable(x->name());
	     string sout = translate_type(tp,false,fout,true);
	     if (stp->eq(#<none>))
	     {  put_in_current_scope(x->name(),tp);
	        mout << sout << " " << x << "; _scoped_variables["
		     << last_scoped_var() << "] = (void*) &" << x << "; ";
	     } else if (!tp->eq(stp))
		odmg_error("Variable has been previously defined with a different type",x);
	     mout << init << "(); ";
	     #case tp
	     | `f(`tp)
		  : collectionp(f)
		  => mout << s << "(" << x << "); ";
	     | _ => mout << x << " = *((" << sout << "*) " << s << "); ";
	     #end;
	   };
  | update(project(`x,`a),`e)
	=> { String s = process_query(#<update(project(`x,`a),`e)>,tp,false,init,true,pq);
	     mout << s << ";";
	   };
  | insert(project(`x,`a),`e)
	=> { String s = process_query(#<insert(project(`x,`a),`e)>,tp,false,init,true,pq);
	     mout << s << ";";
	   };
  | delete(project(`x,`a),`e)
	=> { String s = process_query(#<delete(project(`x,`a),`e)>,tp,false,init,true,pq);
	     mout << s << ";";
	   };
  | delete(`x,`e)
	: x->variablep()
	=> { String es = process_query(e,tp,false,init,true,pq);
	     if (tp->variablep() && classp(tp->name()))
	     {  if (!get_class_extent(tp)->eq(x))
		   odmg_error("Wrong extent name in object deletion -=",x);
		string sout = translate_type(tp,true,fout,true);
		String nm = new_name("X");
		mout << "{ " << init << "(); " << sout << " " << nm << " = (" << sout << ") " << es << "; ";
		string res = "";
		#case get_declaration_binding(new string("_class_indexes"),tp->name())
		| index(...r)
		  => for(; r->consp(); r=r->tl)
			#case get_declaration_binding(r->hd->name(),tp->name())
			| index(_,`unique,...attrs)
			     => {  string key = generate_code(translate_key(variable(nm),attrs,
							new binding<Expr>(nm,tp),new binding<Expr>(nm,tp),-1),false);
				   res = res + "remove_from_index(\"" + *r->hd->name() + "\"," + key + "," + *nm + "); ";
				};
			#end;
		#end;
		mout << res << nm << "->destroy());";
	     } else odmg_error("extent deletion (-=) can only be done for objects");
	   };
  | type(`tp,`v)
	=> {  string st = translate_type(tp,false,fout,true);
	      put_in_current_scope(v->name(),tp);
	      mout << st << " " << v << "; _scoped_variables["
		   << last_scoped_var() << "] = (void*) &" << v << "; ";
	   };
  | define(`name,params(...r),`body)
	=> { if (!name->variablep())
		odmg_error("Methods are not permitted to be defined as macros");
	     Ref<Catalog> dcl = store_declaration(name->name(),define_dcl,e,false);
	   };
  | function(method(`class_name,`name),params(...args),`otype,`body)	/* method body */
	=> { int old_scope = last_scoped_var();
	     set_scope(-1);
	     in_function = true;
	     new_scope();
	     string ot = translate_type(otype,true,fout,true);
	     string ots = translate_type(otype,false,fout,true);
	     mout << ots << " " << class_name << "::" << name << " ( Ref<" << class_name << "> this_ref";
	     fout << "\n/* defined later */\n" << ot << " " << name << "( Ref<" << class_name << "> this_ref";
	     for(list<Expr>* r = args; r->consp(); r=r->tl)
		#case r->hd
		| bind(`v,`tp)
			=> { string stp = translate_type(tp,false,fout,true);
			     mout << ", " << stp << " " << v;
			     fout << ", " << stp << " " << v;
			   };
		#end;
	     mout << ") {\n  " << ot << " res = new (GC) " << ots << ";\n";
	     fout << ");\n\n";
	     mout << "  current_scoped_variable_number += " << args->length()+1 << ";\n";
	     put_in_current_scope(new string("this"),class_name);
	     mout << "  _scoped_variables[current_scoped_variable_number-"
		  << last_scoped_var() << "] = (void*) new (GC) Ref<" << class_name << ">(this_ref);\n  ";
	     for(list<Expr>* r = args; r->consp(); r=r->tl)
		#case r->hd
		| bind(`v,`tp)
			=> { put_in_current_scope(v->name(),tp);
			     mout << "_scoped_variables[current_scoped_variable_number-"
				  << last_scoped_var() << "] = (void*) &" << v << ";\n  ";
			   };
		#end;
	     Expr rotype;
	     Schema lvars = new binding<Expr>;
	     String s = process_query(body,rotype,false,init,true,pq);
	     if (!unify(e,rotype,otype,lvars))
		odmg_error("Wrong type for the returned value of method",otype);
	     mout << init << "(); ";
	     #case otype
	     | `f(`etp)
		  : collectionp(f)
		  => mout << "  " << s << "(*res); ";
	     | _ => mout << "  res = ((" << ot << ") " << s << "); ";
	     #end;
	     mout << "\n  current_scoped_variable_number -= " << args->length()+1 << ";\n  return *res;\n};\n";
	     close_scope();
	     set_scope(old_scope);
	     bool ip = interpreterp;
	     interpreterp = true;
	     Schema sch = type_to_schema(#<struct(...args)>)->extend(#<this>->name(),class_name);
	     Schema stuple = new binding<Expr>;
	     pq = preprocess_expr(translate_query(pq,sch,stuple,false));
	     pq = #<lambda(`otype,bind(this,`class_name),...args,`pq)>;
	     store_declaration(new string(*class_name->name()+"::_"+*name->name()),
			       compiled_method_dcl,pq,false);
	     interpreterp = ip;
	     in_function = false;
	   };
  | function(`name,params(...args),`otype,`body)
	=> { store_declaration(name->name(),define_dcl,e,false);
	     int old_scope = last_scoped_var();
	     set_scope(-1);
	     in_function = true;
	     new_scope();
	     string ot = translate_type(otype,true,fout,true);
	     string ots = translate_type(otype,false,fout,true);
	     mout << ot << " " << name << " ( ";
	     fout << "\n/* defined later */\n" << ot << " " << name << "( ";
	     for(list<Expr>* r = args; r->consp(); r=r->tl)
		#case r->hd
		| bind(`v,`tp)
			=> { string stp = translate_type(tp,true,fout,true);
			     mout << stp << " " << v << ((r->tl->consp()) ? ", " : "");
			     fout << stp << " " << v << ((r->tl->consp()) ? ", " : "");
			   };
		#end;
	     mout << ") {\n  " << ot << " res = new (GC) " << ots << ";\n";
	     fout << ");\n\n";
	     mout << "  current_scoped_variable_number += " << args->length() << ";\n";
	     for(list<Expr>* r = args; r->consp(); r=r->tl)
		#case r->hd
		| bind(`v,`tp)
			=> { put_in_current_scope(v->name(),tp);
			     mout << "_scoped_variables[current_scoped_variable_number-"
				  << last_scoped_var() << "] = (void*) " << v << ";\n  ";
			   };
		#end;
	     Expr rotype;
	     String s = process_query(body,rotype,false,init,true,pq);
	     Schema lvars = new binding<Expr>;
	     if (!unify(e,rotype,otype,lvars))
		odmg_error("Wrong type for the returned value of function",otype);
	     mout << init << "(); ";
	     #case otype
	     | `f(`tp)
		  : collectionp(f)
		  => mout << "  " << s << "(*res); ";
	     | _ => mout << "  res = ((" << ot << ") " << s << "); ";
	     #end;
	     mout << "\n  current_scoped_variable_number -= " << args->length() << ";\n  return res;\n};\n";
	     close_scope();
	     set_scope(old_scope);
	     in_function = false;
	   };
  | create_index(`index_name,`relation,...attrs)
	=> #case class_type(relation->name())
	   | none => odmg_error("Tried to create an index on a nonexistent relation",relation);
	   | `tp => {  Expr extent = get_class_extent(relation);
		       String inm = new_secondary_index(#<index(`index_name,`relation,...attrs)>);
		       Schema sch = (new binding<Expr>)->extend(new string("x"),relation);
		       Expr fkey = translate_key(#<x>,attrs,sch,sch,1);
		       string key = generate_code(#<lambda(key,bind(x,tuple),`fkey)>,false);
		       mout << "create_pool_index(\"" << relation << "\",\"" << extent << "\","
			    << key << ",\"" << inm << "\",false);";
		    };
	   #end;
  | drop_index(`index_name)
	=> odmg_error("drop-index has not been implemented yet");
  | collect(statistics)
	=> mout << "collect_statistics();";
  | print(statistics)
	=> mout << "";
  | print(`e,`depth)
	=> { String s = process_query(e,tp,false,init,true,pq);
	     string sout = translate_type(tp,false,fout,true);
	     String nv = new_name("X");
	     mout << "{ " << sout << "*  " << nv << " = new (GC) " << sout << "; " << init << "(); ";
	     print_scanners(tp);
	     #case tp
	     | `f(`tp)
		  : collectionp(f)
		  => mout << s << "(*" << nv << "); ";
	     | _ => mout << nv << " = ((" << sout << "*) " << s << "); ";
	     #end;
	     mout << " print_value(\"";
	     tp->write(mout);
	     mout << "\",(void*)" << nv << "," << depth << "); };";
	   };
  | initialize()
	=> mout << "ldb_sm->begin_transaction(); login(sm_string(\"admin\"),sm_string(\"pass\")); "
		<< "initialize_current_module(); "
		<< "set_current_module(new string(\"" << current_module_name << "\")); "
		<< "ldb_sm->commit_transaction(); ";
  | begin
	=> mout << "ldb_sm->begin_transaction(); ";
  | abort
	=> mout << "ldb_sm->abort_transaction(); ";
  | commit
	=> mout << "ldb_sm->commit_transaction(); ";
  | cleanup
	=> mout << "cleanup_temp_files(); ";
  | options(...opts)
	=> for(list<Expr>* r=opts; r->consp(); r=r->tl)
	      #case r->hd
	      | bind(persistent_constructions,`n)
			=> persistent_constructions = (n->info.Integer>0);
	      | bind(query_unnesting,`n)
			=> query_unnesting = (n->info.Integer>0);
			   mout << "query_unnesting = " << n << "; ";
	      | bind(pointer_joins,`n)
			=> pointer_joins = (n->info.Integer>0);
			   mout << "pointer_joins = " << n << "; ";
	      | bind(unnests_to_joins,`n)
			=> unnests_to_joins = (n->info.Integer>0);
			   mout << "unnests_to_joins = " << n << "; ";
	      | _ => odmg_error("Unknown option",e);
	      #end;
  #end;
};


extern bool oql_program;

void process ( Expr query ) {
  if (oql_program)
     process_oql(query);
  else {
  Expr e = query->arguments()->tl->hd;
  Expr u = translate(e);
  Schema vars = new binding<Expr>;
  Expr tp = type_of(u,vars,true);
  cout << "\nComprehension Calculus Form:\n";
  u->pretty_print(0,cout);
  cout << endl;
  cout << "\nType of the Query: " << tp;
  Expr oq = optimize_query(u);
  cout << "\n\nOptimized Algebraic Form:\n";
  oq->pretty_print(0,cout);
  Expr pq = best_evaluation_order(oq);
  cout << "\n\nPhysical Plan:\n";
  pq->pretty_print(0,cout);
  cout << "\n\n";
  };
};