/********************************************************************************
*
* File: common.cc
* Title: Tracing and memoization functions used by the optimizer code
* Programmer: Leonidas Fegaras, UTA
* Date: 2/21/97
*
********************************************************************************/


const Expr _EMPTY_NAME_ = variable("");


/* append the plans y to the plans x and remove duplicates */
list<plan*>* merge_plans ( list<plan*>* x, list<plan*>* y ) {
  list<plan*>* res = x;
  bool found;
  for(list<plan*>* r = y; r->consp(); r=r->tl)
  { found = false;
    for(list<plan*>* s = x; !found && s->consp(); s=s->tl)
        found = r->hd->expression->eq(s->hd->expression);
    if (!found) res = res->cons(r->hd);
  };
  return res;
};



/*--------------------------------------------------------------------------------
-  Tracing stuff
--------------------------------------------------------------------------------*/


static int rules2trace[100];


bool in_rules ( int n, const int v[] ) {
  if (v[0])
  {  for(int i = 0; v[i]; i++)
	if (v[i]==n) return true;
  }
  else return true;
  return false;
};


trace ( int level, int rule, string message ) {
  if (!rules2trace[0])
  {  for(int i=level; i>0; i--)
	cout << "   ";
     cout << "At rule " << rule << ": " << message << endl;
  };
};


trace_input ( int level, int rule, Expr e, inherited atrb ) {
  if (in_rules(rule,rules2trace))
  {  for(int i=level; i>0; i--) cout << "   ";
     if (rule==0)
     {  cout << "Rewriting ";
	e->pretty_print(level*2+10);
        cout << endl;
	for(int i=level; i>0; i--) cout << "   ";
	cout << "Inherited: " << atrb << endl;
     }
     else cout << "Trying rule " << rule << " for " << e << ":\n";
  };
};


trace_output ( int level, int rule, list<plan*>* plans ) {
  if (in_rules(rule,rules2trace))
  {  for(int i=level; i>0; i--) cout << "   ";
     if (rule==0) cout << "-->  ";
     else cout << rule << ") -> ";
     if (plans->consp())
     {  cout << plans->hd->expression << "\n";
        for(list<plan*>* r=plans->tl; r->consp(); r=r->tl)
        {  for(int i=level; i>0; i--) cout << "   ";
           cout << "     " << r->hd->expression << endl;
        };
     } else cout << endl;
  };
};


/*--------------------------------------------------------------------------------
-  Memoization function; each rewrite module has its own memo tables
--------------------------------------------------------------------------------*/


static list<memo*>* PHYSICAL_hash_table[hash_size];


hash_table_init ( list<memo*>* hash_table[] ) {
  for(int i=0; i<hash_size; i++)
     hash_table[i] = new list<memo*>;
};


memo* memoize_empty ( list<memo*>* hash_table[], Expr e, inherited atrbs  ) {
  const unsigned long h = e->hash() % hash_size;
  memo* m = new memo(e,atrbs,new list<plan*>);
  hash_table[h] = hash_table[h]->cons(m);
  return m;
};


memo* memoized ( list<memo*>* hash_table[], Expr e, inherited atrbs ) {
  for(list<memo*>* r = hash_table[e->hash() % hash_size]; r->consp(); r = r->tl)
     if (e->eq(r->hd->expression) && eqatrb(atrbs,r->hd->attributes))
        return r->hd;
  return 0;
};



/*--------------------------------------------------------------------------------
-  The default term rewriting in case there is no applicable rule
--------------------------------------------------------------------------------*/


list<plan*>* default_rewrite ( Expr e, inherited atrbs, int level,
			       list<plan*>* (rewrite) (Expr,inherited,int) ) {
  list<plan*>* plans = new list<plan*>;
  if (e->functionp())
  { list<list<plan*>*>* res = (new list<list<plan*>*>)->cons(new list<plan*>);
    for(list<Expr>* r = e->info.Function.Parameters; r->consp(); r=r->tl)
    { list<list<plan*>*>* n = new list<list<plan*>*>;
      for(list<plan*>* p = rewrite(r->hd,atrbs,level+1); p->consp(); p=p->tl)
      { list<list<plan*>*>* m = n;
        for(list<list<plan*>*>* s = res; s->consp(); s=s->tl)
           m = m->cons(s->hd->cons(p->hd));
	n = m;
      };
      res = n;
    };
    for(list<list<plan*>*>* s = res; s->consp(); s=s->tl)
    { list<Expr>* el = Nil;
      synthesized synth = default_synthesized;
      for(list<plan*>* k = s->hd; k->consp(); k=k->tl)
      { el = el->cons(k->hd->expression);
        synth = k->hd->attributes;
      };
      plans = plans->cons(new plan(function(e->info.Function.Name,el),synth));
    };
  }
  else plans = plans->cons(new plan(e,default_synthesized));
  return plans;
};
