#include <cassert>
#include <fstream>
#include <iomanip>
#include <iostream>
#include "AST.h"
#include "MethodDecl.h"
#include "code.h"
#include "compiler.h"
#include "decls.h"
#include "interface.h"
#include "utils.h"
#include "code-util.h"


#if 0

/* DOB: This approach was an interesting idea, but the implementation has a 
 * few subtle bugs which cause incorrect behavior at runtime, and the 
 * optimization (packing the virtual descriptor tables) is of dubious
 * value, so let's do the simple and easy-to-make-correct solution instead
 */

// Check whether i1 is a super-interface of i2
static bool IsSuperInterface(ClassDecl *i1, ClassDecl *i2)
{
    if (i1 == i2)
	return true;

    llist<Decl *> *supers = i2->interfaces();
    ListIterator<Decl *> superIter(supers);

    for (; !superIter.isDone(); superIter.next()) {
	ClassDecl *t = (ClassDecl *)(*superIter);
	if (IsSuperInterface(i1, t))
	    return true;
    }
    
    return false;
}

static Decl *MatchingMethod(MethodDecl &m, ClassDecl &cl)
{
    foriter (decl, cl.environ()->allProperDecls(), EnvironIter) {
	if (decl->category() & Decl::Method) {
          if (!(decl->modifiers() & Common::Abstract) &&
	      decl->container()->category() != Decl::Interface)
	    if ((decl->name() == m.name()) &&
		(decl->type()->paramTypes()->typeIdent(m.type()->paramTypes())))
		return &*decl;
	}
    }
    return NULL;
}

static void ExtendConfList(llist<llist<ClassDecl *> *> *confList,
		    ClassDecl *i1, ClassDecl *i2)
{
    ListIterator<llist<ClassDecl *> *> iter(confList);

//    i1->print(cout); i2->print(cout); cout << "\n****\n";
    for (; !iter.isDone(); iter.next()) {
	if ((*iter)->front() == i1) {
	    llist<ClassDecl *>* members = (*iter)->tail();
	    ListIterator<ClassDecl *> intfIter(members);

	    // Check if already present
	    for (; !intfIter.isDone(); intfIter.next()) {
		if (*intfIter == i2)
		    break;
	    }
	    if (intfIter.isDone()) {
		(*iter)->tail() = cons(i2, members);
	    }
	    break;
	}
    }
    assert (!iter.isDone());
}

static int Conflictp(llist<llist<ClassDecl *> *> *confList,
	      ClassDecl *i1, ClassDecl *i2)
{
    ListIterator<llist<ClassDecl *> *> iter(confList);

    if (i1 == i2)
	return 1;
    
    for (; !iter.isDone(); iter.next()) {
	if ((*iter)->front() == i1) {
	    llist<ClassDecl *>* members = (*iter)->tail();
	    ListIterator<ClassDecl *> intfIter(members);

	    // Check if already present
	    for (; !intfIter.isDone(); intfIter.next()) {
		if (*intfIter == i2)
		    return 1;
	    }
	}
    }
    return 0;
}

static llist<ClassDecl *> *FindAncestors(ClassDecl *intf)
{
    llist<ClassDecl *> *ancestors = NULL;
    llist<Decl *> *supers = intf->interfaces();
    ListIterator<Decl *> superIter(supers);

    for (; !superIter.isDone(); superIter.next()) {
	ClassDecl *t = (ClassDecl *)(*superIter);
	ancestors = cons(t, ancestors);
	ancestors = extend(ancestors, FindAncestors(t));
    }
    return ancestors;
}

static void IntraConflicts(ClassDecl *intf, llist<llist<ClassDecl *> *> *confList)
{
    llist<ClassDecl *> *ancestors = FindAncestors(intf);

    foriter (p, ancestors, ListIterator<ClassDecl *>) {
	ExtendConfList(confList, intf, *p);
    }

    free_all(ancestors);
}

static void PairwiseConflicts(TreeNode *intfs, llist<llist<ClassDecl *> *> *confList)
{
    foriter (p, intfs->allChildren(), TreeNode::ChildIter) {
	foriter (q, intfs->allChildren(), TreeNode::ChildIter) {
	    if (*p != *q) {
		ClassDecl *i1, *i2;

		i1 = (ClassDecl *)(*p)->name()->decl();
		i2 = (ClassDecl *)(*q)->name()->decl();

		llist<ClassDecl *> *list1 = cons(i1, FindAncestors(i1));
		llist<ClassDecl *> *list2 = cons(i2, FindAncestors(i2));

		foriter (t1, list1, ListIterator<ClassDecl *>) {
		    foriter (t2, list2, ListIterator<ClassDecl *>) {
			ExtendConfList(confList, *t1, *t2);
		    }
		}
		
		free_all(list1);
		free_all(list2);
	    }
	}
    }
}

// We store a list of list of methods.  Each list is a set of
// non-conflicting methods, so they can share the same id.
static llist<llist<MethodDecl *> *> *methodLists = NULL;

static int AssignUniqueId(MethodDecl *m, llist<llist<ClassDecl *> *> *confList)
{
    ListIterator<llist<MethodDecl *> *> iter(methodLists);
    ClassDecl *i1 = (ClassDecl *)m->container();
    int i;
    
    for (i=0; !iter.isDone(); iter.next(), i++) {
	llist<MethodDecl *>* target = (*iter);
	ListIterator<MethodDecl *> targetIter(target);

	for (; !targetIter.isDone(); targetIter.next()) {
	    ClassDecl *i2 = (ClassDecl *)((*targetIter)->container());
	    if (Conflictp(confList, i1, i2))
		break;
	}
	if (targetIter.isDone()) {
	    (*iter) = cons(m, target);
//	    cout << "Assigning " << i << " to: ";
//	    m->print(cout);
//	    cout << endl;
	    return i;
	}
    }

//    cout << "Assigning " << i << " to: ";
//    m->print(cout);
//    cout << endl;
    
    // Could not find a target list where all methods where non-conflicting.
    methodLists = extend(methodLists, cons(cons(m)));
//    methodLists = cons(cons(m), methodLists);
    return i;
}

int FindIntfMethodId(const MethodDecl &m)
{
    ListIterator<llist<MethodDecl *> *> iter(methodLists);
    int i;

    for (i=0; !iter.isDone(); iter.next(), i++) {
	llist<MethodDecl *>* bucket = (*iter);
	ListIterator<MethodDecl *> buckIter(bucket);

	for (; !buckIter.isDone(); buckIter.next()) {
	    if ((*buckIter) == &m)
		return i;
	}
    }
    fatal_error("");
    return -1;
}


#if 0
static bool ImplementsMethod(MethodDecl *m, ClassDecl *cl)
{
    llist<Decl *> *intfs = cl->interfaces();
    ListIterator<Decl *> intfIter(intfs);
    ClassDecl *methCont = (ClassDecl *)m->container();

    for (; !intfIter.isDone(); intfIter.next()) {
	if (methCont == (*intfIter))
	    return true;
    }
    return false;
}
#endif


void EmitIntfMT(ClassDecl &cl, ostream& os)
{
    const string mtName = cl.cIntfMTName();
    
    os << "void (*" << mtName << "[])() = ";

    if (cl.interfaces() == NULL) {
        /* Put someting in the braces even though nothing is needed. Some
	   C compilers with balk without it. */
	os << "{ NULL };\n";
	return;
    }

    os << "{\n";

    bool first = true;
    ListIterator<llist<MethodDecl *> *> iter(methodLists);
    for (; !iter.isDone(); iter.next()) {
	llist<MethodDecl *>* bucket = (*iter);
	ListIterator<MethodDecl *> buckIter(bucket);

	if (first) first = false; else os << ",";
	
	for (; !buckIter.isDone(); buckIter.next()) {
	    Decl *match = MatchingMethod(**buckIter, cl);
	    if (match) {
		os << "\n (void (*)())" << match->cMethodNameStatic();
		break;
	    }
	}
	if (buckIter.isDone()) {
	    os << "\n NULL";
	}
    }
    
    os << "\n};\n";
}

void CreateIntfMethods()
{
  llist<llist<ClassDecl *> *> *confList = NULL;
  
  // Build a list of lists.  Each list has an interface as the
  // head element with the rest of the list containing the interfaces
  // that conflict with the head element. 
  
  // First build a list of lists with head elements
  foreach (f, llist<CompileUnitNode *>, *allFiles)
    foriter (type, (*f)->types()->allChildren(), TreeNode::ChildIter)
      if (strcmp((*type)->oper_name(), "InterfaceDeclNode") == 0)
	confList = cons(cons((ClassDecl *)(*type)->decl()), confList);
  
  // Insert the conflicts in the conflict list based on interface hierarchy
  foreach (f, llist<CompileUnitNode *>, *allFiles)
    foriter (type, (*f)->types()->allChildren(), TreeNode::ChildIter)
      if (strcmp((*type)->oper_name(), "InterfaceDeclNode") == 0)
	IntraConflicts((ClassDecl *)(*type)->decl(), confList);
    
  // Insert the conflicts in the conflict list based on class definitions
  foreach (f, llist<CompileUnitNode *>, *allFiles)
    foriter (type, (*f)->types()->allChildren(), TreeNode::ChildIter)
      if (strcmp((*type)->oper_name(), "ClassDeclNode") == 0)
	PairwiseConflicts((*type)->interfaces(), confList);

  // Now iterate over all the interface methods to emit unique ids
  foreach (f, llist<CompileUnitNode *>, *allFiles)
    foriter (type, (*f)->types()->allChildren(), TreeNode::ChildIter)
      if (strcmp((*type)->oper_name(), "InterfaceDeclNode") == 0) {
	TreeNode *intf = (*type);
	
	foriter (member, intf->members()->allChildren(), TreeNode::ChildIter)
	  if (strcmp((*member)->oper_name(), "MethodSignatureNode") == 0)
	    AssignUniqueId((MethodDecl *)(*member)->simpName()->decl(), confList);
    }
}
#else

//-------------------------------------------------------------------------------------------
// A simpler but correct implementation

// return a list of all the interface decls which are supertypes of this class/interface
llist<ClassDecl *>* getAllInterfaces(ClassDecl *cd) {
  llist<ClassDecl *> *retval = NULL;
  if (cd->category() == Decl::Interface) 
    retval = cons(cd);
  llist<Decl *> *p = cd->interfaces();
  while (p) {
    ClassDecl *q = (ClassDecl *)p->front();
    p = p->tail();
    retval = extend(retval, getAllInterfaces(q));
  }
  if (cd != ObjectDecl && cd->superClass()) {
    retval = extend(retval, getAllInterfaces(cd->superClass()));
  }
  return retval;
}

// for a given class cd, return the decl for the method which implements the given method signature
// (or NULL if no implementation is found)
MethodDecl *findMethodImplementation(ClassDecl *cd, MethodDecl *signaturedecl) {
  assert(cd->category() == Decl::Class && isMethodSignatureNode(signaturedecl->source()));
  foriter (decl, cd->environ()->allProperDecls(), EnvironIter) {
      if (decl->category() & Decl::Method) {
        if (!(decl->modifiers() & Common::Abstract))
	  if ((decl->name() == signaturedecl->name()) &&
            (decl->type()->paramTypes()->typeIdent(signaturedecl->type()->paramTypes()))) {
            assert(isMethodDeclNode(decl->source()));
	    return dynamic_cast<MethodDecl *>(&*decl);
          }
      }
  }
  return NULL;
}

map <MethodDecl *, int> intfMethodId;

void CreateIntfMethods() {
  // assign a unique integer index to each method signature in any interface in the system
  // interface virtual dispatch will use this index to find the correct implementation
  // in the interface dispatch table for the target object
  //
  // DOB: subtle bug: this numbering may be inconsistent between a tlib compile and application compile
  //  however, it's so unlikely this bug will ever be observed that it's not worth fixing right now
  intfMethodId.clear();
  int id=0;

  foreach (f, llist<CompileUnitNode *>, *allFiles)
    foriter (type, (*f)->types()->allChildren(), TreeNode::ChildIter)
      if (strcmp((*type)->oper_name(), "InterfaceDeclNode") == 0) {
	TreeNode *intf = (*type);
	
	foriter (member, intf->members()->allChildren(), TreeNode::ChildIter)
          if (isMethodSignatureNode(*member)) {
            MethodDecl *md = dynamic_cast<MethodDecl *>((*member)->decl());
            assert(md != NULL);
            assert(intfMethodId.count(md) == 0);
            intfMethodId[md] = id++;
          }
      }
}
void EmitIntfMT(ClassDecl &cl, ostream& os) {
    const string mtName = cl.cIntfMTName();
    os << "void (*" << mtName << "[])() = ";

    map<int, string> mt;
    llist<ClassDecl *>* interfacelist = getAllInterfaces(&cl);

    if (interfacelist == NULL || 
        (cl.modifiers() & Common::Abstract) ||
        (cl.modifiers() & Common::Immutable) ||
        (cl.category() & Decl::Interface)) {
      free_all(interfacelist);
      /* Put someting in the braces even though nothing is needed. Some
	 C compilers with balk without it. */
      os << "{ NULL };\n";
      return;
    }

    os << "{\n";
    int maxid = -1;
    while (interfacelist) {
      ClassDecl *intf = interfacelist->front();
      interfacelist = interfacelist->free();

      assert(intf->category() == Decl::Interface);
      foriter (member, intf->source()->members()->allChildren(), TreeNode::ChildIter) {
        if (isMethodSignatureNode(*member)) {
          MethodDecl *signaturedecl = (MethodDecl *)(*member)->decl();
	  MethodDecl *match = findMethodImplementation(&cl, signaturedecl);
          assert(match != NULL);
          assert(intfMethodId.count(signaturedecl) == 1);
          int id = intfMethodId[signaturedecl];
	  mt[id] = match->cMethodNameStatic();
          if (id > maxid) maxid = id;
        }
      }
    }

    for (int i=0; i <= maxid; i++) {
      if (mt.count(i)) 
        os << " (void (*)())" << mt[i] << ",\n";
      else 
        os << " NULL,\n";
    }
    os << " NULL\n};\n"; // make sure we have at least one entry
}

int FindIntfMethodId(const MethodDecl &m) {
  MethodDecl *md = (MethodDecl*)&m;
  assert(isMethodSignatureNode(md->source()));
  assert(intfMethodId.count(md) == 1);
  return intfMethodId[md];
}

#endif