/*------------------------------------------------------------\
|                                                             |
| Tool    :                  systemcass                       |
|                                                             |
| File    :                  process_dependancy.cc            |
|                                                             |
| Author  :                 Buchmann Richard                  |
|                                                             |
| Date    :                   21_09_2004                      |
|                                                             |
\------------------------------------------------------------*/

/* 
 * This file is part of the Disydent Project
 * Copyright (C) Laboratoire LIP6 - Département ASIM
 * Universite Pierre et Marie Curie
 * 
 * Home page          : http://www-asim.lip6.fr/disydent
 * E-mail             : mailto:richard.buchmann@lip6.fr
 * 
 * This library is free software; you  can redistribute it and/or modify it
 * under the terms  of the GNU Library General Public  License as published
 * by the Free Software Foundation; either version 2 of the License, or (at
 * your option) any later version.
 * 
 * Disydent 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 the GNU C Library; see the  file COPYING. If not, write to the Free
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include <set>
#include <iostream>
#include <fstream>
#include "assert.h"
#include "process_dependency.h"
#include "methodprocess_dependency.h"
#include "simplify_string.h"
#include "sc_fwd.h"
#include "sc_module.h"
#include "sc_ver.h"

using namespace std;

namespace sc_core {

bool 
ProcessDependency::operator < (const ProcessDependency &a) const
{
	if (a.source < source)
		return false;
	if (a.destination < destination)
		return false;
	return true;
}

static
void
dot_write (ofstream &o,
           const ProcessDependencyGraph &g)
{
	string s;
	ProcessDependencyGraph::const_iterator it;
	for (it = g.begin (); it != g.end (); ++it)
	{
		string name;
		name = it->source->module->name();
		name += "_";
		name += it->source->name;
		o << simplify_name(name.c_str(),s);
		o	<< " -> ";
		name = it->destination->module->name();
		name += "_";
		name += it->destination->name;
		o << simplify_name(name.c_str(),s);
	  o << "\n";
	}
}

static
void
dot_write (ofstream &o, 
           const ProcessDependencyList &l)
{
	const method_process_t *old = NULL;
	string s;
	ProcessDependencyList::const_iterator it;
	for (it = l.begin (); it != l.end (); ++it)
	{
		const method_process_t *current = *it;
		if (old)
		{
			string name;
			name = old->module->name();
			name += "_";
			name += old->name;
			o << simplify_name(name.c_str(),s);
			o	<< " -> ";
			name = current->module->name();
			name += "_";
			name += current->name;
			o << simplify_name(name.c_str(),s);
		  o << "\n";
		}
		old = current;
	}
}

bool
ProcessDependencyGraph2dot (const char *name,
                            const ProcessDependencyGraph& g)
{
	if (!name)
		return false;
	string filename;
	filename =  name;
	filename += ".dot";
	ofstream o;
  o.open (filename.c_str(),ios::out | ios::trunc);
	if (o.is_open () == false)
		return false;
	o << "// Ordered process list\n"
             "// Generated by "
          << sc_version () << "\n";
	o << "strict digraph " << name << " {\n";
	dot_write (o,g);
	o << "}\n";
	o.close ();
  if (dump_stage)
    cerr << "Port Dependency Graph written into '" 
         << filename << "'.\n";
	return true;
}

bool
ProcessDependencyList2dot (const char *name,
                          const ProcessDependencyList& l)
{
	if (!name)
		return false;
	string filename;
	filename =  name;
	filename += ".dot";
	ofstream o;
  o.open (filename.c_str(),ios::out | ios::trunc);
	if (o.is_open () == false)
		return false;
	o << "// Ordered process list\n"
       "// Generated by "
    << sc_version () << "\n";
	o << "digraph " << name << " {\n";
	dot_write (o,l);
	o << "}\n";
	o.close ();
	return true;
}

#if 0
ProcessDependencyGraph* 
sc_core::MakeProcessDependencyGraph (const SignalDependencyGraph& g)
{
  if (dump_stage)
	  cerr << "Making module dependency graph...\n";

	ProcessDependencyGraph *mod_g = new ProcessDependencyGraph ();
	SignalDependencyGraph::const_iterator it;
	for (it = g.begin(); it != g.end(); ++it)
	{
		ProcessDependency s;
		s.destination = it->method;
	  SignalDependencyGraph::const_iterator it2;
		for (it2 = g.begin(); it2 != g.end(); ++it2)
	  {
			if (it2->source == it->destination)
			{
	  		s.source = it2->method;
  	    mod_g->insert(s);
			}
		}
	}
	return mod_g;
}

static
const method_process_t*
get_method (const equi_t &e, const SignalDependencyGraph &sig)
{
	SignalDependencyGraph::const_iterator it;
	for (it = sig.begin (); it != sig.end (); ++it)
	{
		if (it->destination == &e)
			return it->method;
	}
	return NULL;
}
#endif


static
bool
is_leef (const SignalDependencyGraph &g,
         const equi_t                *e)
{
	SignalDependencyGraph::const_iterator it;
	for (it = g.begin (); it != g.end (); ++it)
  {
    if (it->source == e)
      return false;
  }
  return true;
}

static
bool
has_all_leef (const SignalDependencyGraph &sig,
              const method_process_t      *m)
{
	SignalDependencyGraph::const_iterator sig_it;
	for (sig_it = sig.begin (); sig_it != sig.end (); ++sig_it)
    if ((sig_it->method == m) 
       && (!is_leef (sig, sig_it->destination)))
      return false;
  return true;
}

static
const method_process_t*
get_best_process (const SignalDependencyGraph &sig)
{
	SignalDependencyGraph::const_iterator sig_it;
	for (sig_it = sig.begin (); sig_it != sig.end (); ++sig_it)
  {
    if (has_all_leef (sig, sig_it->method)) 
      return sig_it->method;
  }
  return NULL;
}

/*
 *   Remove signals
 */
static
void
remove_leefs (SignalDependencyGraph  &g,
             const method_process_t &m)
{
	SignalDependencyGraph::iterator it;
	it = g.begin (); 
  while (it != g.end ())
  {
    const method_process_t *cur_m = it->method;
    if ((cur_m == &m) && (is_leef (g,it->destination)))
    {
      SignalDependencyGraph::iterator x = it++;
      g.erase (x);
    }
    else
      ++it;
  }	
}

#if defined(UNUSED)
static
void
print_signals (ostream                      &o,
               const SignalDependencyGraph  &sig,
               const method_process_t       *method,
               bool                          source)
{
  int count = 0;
	SignalDependencyGraph::const_iterator it;
	for (it = sig.begin (); it != sig.end (); ++it)
  {
    const SignalDependency &dep   = *it;
    const method_process_t *cur_m = dep.method;
    if (cur_m == method)
    {
      const equi_t *e = (source)?dep.source:dep.destination;
      o << ((count++)?",":"") << get_name (*e);
    }
  }	
}
#endif

static
void
print_leef_list (SignalDependencyGraph &sig)
{
  typedef map<const equi_t *, const method_process_t *> table_t;
  table_t table;
  
  // For each arrow, add destination node into table
	SignalDependencyGraph::const_iterator sig_it;
	for (sig_it = sig.begin (); sig_it != sig.end (); ++sig_it)
  {
    const SignalDependency  sd     = *sig_it;
    const equi_t           *equi   = sd.destination;
	  const method_process_t *method = sd.method;
    table[equi] = method;
  }
 
  // For each arrow, remove source node into table
	for (sig_it = sig.begin (); sig_it != sig.end (); ++sig_it)
  {
    const SignalDependency  sd = *sig_it;
    const equi_t           *e  = sd.source;
    table_t::const_iterator tab_it = table.find (e);
    if (tab_it != table.end ())
      table.erase (e);
  }

  typedef multimap<const method_process_t *, const equi_t *> table2_t;
  typedef pair<const method_process_t *, const equi_t *> table2_pair_t;
  table2_t table2;

  // Build table2
  table_t::const_iterator it;
  for (it = table.begin(); it != table.end(); ++it)
  {
    const method_process_t *method = it->second;
    const equi_t           *equi   = it->first;
    table2_pair_t           pair   = table2_pair_t(method,equi);
    table2.insert(pair);
  }

  // Print leef list
  cerr << "Please split following methods :";
  table2_t::const_iterator low_it = table2.begin();
  table2_t::const_iterator up_it;
  while (low_it != table2.end ())
  {
    const method_process_t *method      = low_it->first;
    const char             *method_name = method->name;
    const sc_module        *module      = method->module;
    const char             *module_name = module->name();
    cerr << "\n\t - " << module_name << "::" << method_name;
    cerr << "() to evaluate '";
    int   count = 0;
    up_it = table2.upper_bound(low_it->first);
    table2_t::const_iterator it2;
    for (it2 = low_it; it2 != up_it; ++it2)
    {
      const equi_t *equi         = it2->second;
      const char   *signal_name  = get_name (*equi);
      cerr << ((count++)?",":"") << signal_name;
    }
    cerr << "' signal(s) separetly";
    low_it = up_it;
  }
  cerr << "\n";
}

static
void
help2resolve (SignalDependencyGraph &sig)
{
  print_leef_list (sig);
  MethodProcessDependencyGraph2dot ("methodprocess_graph", sig);
  cerr << "Please look at 'methodprocess_graph.dot' "
          "to know how to get ride of circular dependencies.\n";
  if (dump_all_graph)
  {
    SignalDependencyGraph2dot ("reduced_signal_graph", sig);
  }
}

ProcessDependencyList* 
MakeProcessDependencyList  (const SignalDependencyGraph  & _sig_g)
{
  if (dump_stage)
    cerr << "Making process dependency list...\n";
	ProcessDependencyList *mod_l = new ProcessDependencyList ();
	SignalDependencyGraph sig_g = _sig_g;
	while (!sig_g.empty ())
	{
		const method_process_t *process = get_best_process (sig_g);
#if 1
    if (process == NULL)
    {
      cerr << "Internal Error : Unable to select the best process to schedule.\n";
      help2resolve (sig_g);
      exit (31032005); // 197
    }
#endif
	  mod_l->push_front(process);
#if 0
		cerr << "Process found : " << *process << "\n";
#endif
		remove_leefs (sig_g, *process);
	}
	return mod_l;
}

} // end of sc_core namespace