#include "AST.h"
#include "TouchSet.h"
#include "Bridge.h"
#include "cfg.h"
#include "optimize.h"
#include "pseudocode.h"

extern void fixParents(TreeNode *t);
extern TreeNode *fixSubtreeSharing(TreeNode *t);
extern bool debug_stoptifu;

/* Macros for debugging output */
#undef DPRINT
#undef DPRINTLN
#undef DBG
#define DPRINT(x) do { if (debug_stoptifu) cout << (x); } while (0) 
#define DPRINTLN(x) DPRINT(string(x) + '\n')
#define DBG(x) do { if (debug_stoptifu) { x; } } while (0)
#undef XPRINT
#undef XPRINTLN
#undef XBG
#define XPRINT(x) do { if (1) cout << (x); } while (0) 
#define XPRINTLN(x) XPRINT(string(x) + '\n')
#define XBG(x) do { if (1) { x; } } while (0)


/* True iff:
   1. the only way to enter the Bridge is from t OR
   2. t is a foreach+ and the only way to enter the Bridge is from t or from
      t's enclosing IfStmtNode. */
bool Bridge::must_come_from(TreeNode *t)
{
  assert(finalized);
  if (everything.empty())
    return true;
  bool result = true;
  bool should_add_and_remove = (everything.find(t) == everything.end());
  TreeNode *t2 = (isForEachStmtNode(t) ?
		  static_cast<ForEachStmtNode *>(t)->cannotBeEmpty() :
		  NULL);
  if (should_add_and_remove) {
    everything.insert(t);
    if (t2 != NULL)
      everything.insert(t2);
  }

  for (treeSet::iterator j = everything.begin(); j != everything.end(); j++) {
    const TreeNode *i = *j;
    if (i != t && i != t2 && i->isStatementNode())
      if (!::must_come_from(static_cast<const StatementNode *>(i), everything)) {
	result = false;
	DPRINT("Bridge::must_come_from failed(): this node\n");
	DBG(i->pseudoprint(cout));
	DPRINT("\ndoesn't have to come from\n");
	DBG(t->pseudoprint(cout));
	goto done;
      }
  }

 done:
  if (should_add_and_remove) {
    everything.erase(t);
    if (t2 != NULL)
      everything.erase(t2);
  }
  return result;
}

TouchSet *Bridge::reads(bool ignore_junk_method)
{
  assert(finalized);
  TouchSet *&r = ignore_junk_method ? r1 : r0;
  if (r == NULL) {
    for (treeSet::iterator i = everything.begin(); i != everything.end(); i++)
      r = TouchSet_union(r, ::reads(*i, ignore_junk_method));
  }
  return r;
}

TouchSet *Bridge::writes(bool ignore_junk_method)
{
  assert(finalized);
  TouchSet *&w = ignore_junk_method ? w1 : w0;
  if (w == NULL) {
    for (treeSet::iterator i = everything.begin(); i != everything.end(); i++)
      w = TouchSet_union(w, ::writes(*i, ignore_junk_method));
  }
  return w;
}

/* Adjoin (to ss) statements that cover everything in this Bridge. */
void Bridge::add_statements(set<StatementNode *> &ss)
{
  assert(finalized);
  for (treeSet::iterator i = everything.begin(); i != everything.end(); i++)
    ss.insert(enclosingStmt(*i));
}

/* Adjoin (to ss) decls that are necessary for the statements in stmt_list. */
void Bridge::add_decls(treeSet &ss)
{
  assert(finalized);
  if (decl_list != NULL)
    foreach (p, llist<TreeNode *>, *decl_list)
      ss.insert(*p);
}

/* True if the bridge includes the given statement in its entirety. */
bool Bridge::stmt_is_included(StatementNode *t)
{
  bool r = (stmt_set.find(t) != stmt_set.end());
  // t = (StatementNode *) fixSubtreeSharing(t);
  if (!r) {
    llist<StatementNode *> *todo = all_substmts(t);
    if (contains(todo, t)) {
      t->error() << "Internal error: statement\n" << pseudocode(t) <<
	"\ncontains itself as a substatement\n";
      fatal_error("");
    }
    if (todo != NULL) {
      do {
	if (!stmt_is_included(todo->front())) {
	  free_all(todo);
	  DPRINTLN("Check if included " + pseudocode(t) + ": NO");
	  return false;
	}
	todo = todo->free();
      } while (todo != NULL);
      r = true;
    }
  }
  DPRINTLN("Check if included " + pseudocode(t) + ": " + (r ? "YES" : "NO"));
  return r;
}

/* Helper for finalize().  Adds the largest StatementNode subtree that
   contains t and that is wholly in this Bridge to the ordered list of
   statements in this Bridge (if it is not already present). */
void Bridge::next_stmt_is(StatementNode *t)
{
  StatementNode *good_t, *t0 = t;
  DPRINTLN("next_stmt_is(" + pseudocode(t0) + ")");
  if (t == NULL || contains(stmt_list, t) || !stmt_is_included(t))
    return;
  do {
    good_t = t;
    t = enclosingStmt(t->parent());
    assert(t != good_t);
    DBG({
      char s[80];
      sprintf(s, "enclosingStmt(%lx) is %lx\n",
	      (long) good_t->parent(), (long) t);
      cout << s;
    });
    DPRINTLN("checking statement " + pseudocode(t));
  } while (t != NULL && stmt_is_included(t));
  if (!contains(stmt_list, good_t)) {
    DPRINTLN("next_stmt_is(" + pseudocode(t0) + "): "
	     "adding to bridge's stmt_list:" + pseudocode(good_t));
    push(stmt_list, good_t);
  } else 
    DPRINTLN("next_stmt_is(" + pseudocode(t0) + "): "
	     "no action needed");
}

/* Push statements in b onto stmt_list; push everything else onto decl_list. */
static void dissect_block(BlockNode *b, llist<StatementNode *> *&stmt_list,
			  llist<TreeNode *> *&decl_list)
{
  foriter (p, b->stmts()->allChildren(), TreeNode::ChildIter)
    if ((*p)->isStatementNode())
      push(stmt_list, static_cast<StatementNode *>(*p));
    else
      push(decl_list, *p);
}

/* Add BlockNodes in l to s. */
static void getBlockNodes(llist<StatementNode *> *l, set<BlockNode *> &s)
{
  foreach (st, llist<StatementNode *>, *l)
    if (isBlockNode(*st))
      s.insert(static_cast<BlockNode *>(*st));
}

/* If t appears in stmt_list then remove it.  If t appears at top
   level of a block in stmt_list then remove it and put everything
   else in that block onto stmt_list and decl_list.  May destructively
   modify all args except t.  Also, remove any elements of everything
   that have t as an ancestor.  */
static void remove12(StatementNode *t,
		     llist<StatementNode *> *&stmt_list,
		     llist<TreeNode *> *&decl_list,
		     treeSet *everything)
{
  llist<StatementNode *> *new_stmt_list = NULL;
  foreach (s, llist<StatementNode *>, *stmt_list) {
    if (isBlockNode(*s)) {
      BlockNode *b = static_cast<BlockNode *>(*s);
      if (block_contains(t, b)) {
	dissect_block(b, new_stmt_list, decl_list);
	continue;
      }
    }
    push(new_stmt_list, *s);
  }
  free_all(stmt_list);
  stmt_list = new_stmt_list;
  if (contains(stmt_list, t))
    stmt_list = remove(t, stmt_list);

  llist<TreeNode *> *i;
  for (i = set_to_list(everything); i != NULL; i = i->free()) {
    if (isAncestor(t, i->front()))
      everything->erase(i->front());
  }
}

/* Construct a ordered list of statements that comprise the bridge.
   Put that list in stmt_list.  Exclude the given loops and their
   enclosing if stmts, if any.  If the bridge appears to be a single
   BlockNode then put the constituent statements and decls in that
   BlockNode onto stmt_list and decl_list, respectively. */
void Bridge::finalize(llist<ForEachStmtNode *> *exclude)
{
  DPRINTLN("finalize()");
  decl_list = NULL;
  for (llist<TreeNode *> *i = l; i != NULL; i = i->tail()) {
    stmt_set.insert(enclosingStmt(i->front()));
    everything.insert(i->front());
  }
  {
    set<StatementNode *> done;
    for (llist<TreeNode *> *i = l; i != NULL; i = i->tail()) {
      TreeNode *t = i->front();
      if (!t->absent()) {
	StatementNode *st = enclosingStmt(t);
	if (st != NULL && !st->absent() && done.find(st) == done.end()) {
	  DBG({
	    string statement_text = pseudocode1(st);
	    if (statement_text == "" && isDummyNode(st))
	      statement_text = "DUMMY " + pseudocode1(st->expr());
	    XPRINTLN("finalize(): incorporate stmt " + statement_text);
	    if (statement_text == "") {
	      cout << "huh? ";
	      st->print(cout, 0);
	      cout << endl;
	      cout << "parent is ";
	      if (st->parent() != NULL)
		st->parent()->print(cout, 0);
	      else
		cout << "NULL";
	      cout << endl;
	    }
	  });
	  next_stmt_is(st);
	  done.insert(st);
	}
      }
    }
  }
  set<BlockNode *> original_blocks;
  getBlockNodes(stmt_list, original_blocks);
  if (exclude != NULL) {
    while (exclude != NULL) {
      ForEachStmtNode *x = exclude->front();
      DPRINTLN("Exclude from bridge: " + pseudocode(x));
      remove12(x, stmt_list, decl_list, &everything);
      StatementNode *y = dynamic_cast<StatementNode *>(x->cannotBeEmpty());
      DPRINTLN("Exclude from bridge: " + pseudocode(y));
      if (y != NULL)
	remove12(y, stmt_list, decl_list, &everything);
      exclude = exclude->tail();
    }
    /* Expand blocks that are not in the original program */
    llist<StatementNode *> *new_stmt_list = NULL;    
    foreach (q, llist<StatementNode *>, *stmt_list)
      if (isBlockNode(*q) &&
	  original_blocks.find(static_cast<BlockNode *>(*q)) ==
	  original_blocks.end()) {
	dissect_block(static_cast<BlockNode *>(*q), new_stmt_list, decl_list);
	delete *q;
      } else
	push(new_stmt_list, *q);
    stmt_list = dreverse(new_stmt_list);
  }
  /* If the whole of the decls and stmts is one block then expand it (why?). */
  while (decl_list == NULL && stmt_list->size() == 1 &&
	 isBlockNode(stmt_list->front())) {
    BlockNode *b = static_cast<BlockNode *>(stmt_list->front());
    stmt_list = stmt_list->free(); // free the one cons cell and start over
    dissect_block(b, stmt_list, decl_list);
  }
  stmt_list = dreverse(stmt_list);
  free_all(l);
  l = NULL;
  /* Rebuild stmt_set to reflect exact contents of stmt_list. */
  stmt_set.clear();
  for (llist<StatementNode *> *i = stmt_list; i != NULL; i = i->tail())
    stmt_set.insert(i->front());
  finalized = true;
  DBG({
    cout << "stmt_list->size() = " << stmt_list->size() << endl;
    cout << "decl_list->size() = " << decl_list->size() << endl;
    cout << "Finalized Bridge contains the following decls:" << endl;
    for (llist<TreeNode *> *i = decl_list; i != NULL; i = i->tail())
      i->front()->pseudoprint(cout, 0);
    cout << endl << endl <<
      "Finalized Bridge contains the following stmts:" << endl;
    for (llist<StatementNode *> *i = stmt_list; i != NULL; i = i->tail())
      PLCODE(i->front());
    cout << endl << endl <<
      "Finalized Bridge's `everything' set contains the following:" << endl;
    for (treeSet::iterator i = everything.begin(); i != everything.end(); i++)
      cout << pseudocode(*i) << ' ';
    cout << endl << "End of finalized Bridge" << endl << endl; 
  });
}

void Bridge::push_contents(llist<TreeNode *> *& l)
{
  foreach (s, llist<TreeNode *>, *decl_list)
    push(l, *s);
  foreach (s, llist<StatementNode *>, *stmt_list)
    push(l, (TreeNode *) *s);
}